MathDB

Recursive problem

Source: András Imolay, Budapest

March 10, 2021

Sequencenumber theory

Problem Statement

Let

k > 1

be a fixed odd number, and for non-negative integers

n

let

f_n=\sum_{\substack{0\leq i\leq n\\ k\mid n-2i}}\binom{n}{i}.

Prove that

f_n

satisfy the following recursion:

f_{n}^2=\sum_{i=0}^{n} \binom{n}{i}f_{i}f_{n-i}.