Mathematical Reflections 2011, Issue 6 - Problem O212

Problem:
Let $f_0(i)=1$ for all $i \in \mathbb{N}$ and let $f_k(n)=\displaystyle \sum_{i=1}^n f_{k-1}(i)$ for $k \geq 1$. Prove that
$$\sum_{j=0}^{\lfloor \frac{n}{2} \rfloor} f_j(n-2j)=F_n,$$ where $F_n$ is the $n$-th Fibonacci number.

Proposed by Ivan Borsenco.

Solution:
First we show that if $n,k \geq 1$, then
\begin{equation}\label{identity1}
\sum_{i=k}^{n} {i \choose k} = {n+1 \choose k+1}. \qquad (1)
\end{equation}
By Pascal's Identity,
$$\begin{array}{lll} \displaystyle \sum_{i=k}^{n} {i \choose k} & = &  \displaystyle {k \choose k+1} + \sum_{i=k}^{n} {i \choose k}\\
& = & \displaystyle {k+1 \choose k+1} + \sum_{i=k+1}^{n} {i \choose k} \\ & = & \displaystyle {k+2 \choose k+1} + \sum_{i=k+2}^{n} {i \choose k} \\ & = & \displaystyle \vdots \\ & = & \displaystyle {n+1 \choose k+1}. \end{array}$$
Now, we prove by induction on $k \geq 1$ that $f_k(n)=\displaystyle {n+k-1 \choose k}$ for any $n \in \mathbb{N}$.
For $k=1$ we have $f_1(n)=\displaystyle \sum_{i=1}^n f_{0}(i)=n$, so the equality holds. Suppose that the equality is true for $k$. Then
$$f_{k+1}(n)=\sum_{i=1}^n f_{k}(i)=\sum_{i=1}^n {i+k-1 \choose k} = {n+k \choose k+1}$$ by (1). Now, it is clear that $$\sum_{j=0}^{\lfloor \frac{n}{2} \rfloor} f_j(n-2j) = \sum_{j=0}^{\lfloor \frac{n}{2}  \rfloor} {n-j-1 \choose j}.$$ So, we only have to prove that $$\sum_{j=0}^{\lfloor \frac{n}{2}  \rfloor} {n-j-1 \choose j}=F_n,$$ where $F_n$ is the $n$-th Fibonacci number. This can be done by induction on $n$. For $n=1$ and $n=2$ is obvious. Suppose that the equality holds for every $m$ such that $1 \leq m \leq n$. Since $\lfloor \frac{n-1}{2}  \rfloor + 1 = \lfloor \frac{n+1}{2} \rfloor$, we have
$$\begin{array}{lll} F_{n-1}+F_{n} & = & \displaystyle \sum_{j=0}^{\lfloor \frac{n-1}{2}  \rfloor} {n-j-2 \choose j} + \sum_{j=0}^{\lfloor \frac{n}{2}  \rfloor} {n-j-1 \choose j} \\ & = & \displaystyle {n-1 \choose 0} + \sum_{j=1}^{\lfloor \frac{n+1}{2}  \rfloor}\left[{n-j-1 \choose j-1} + {n-j-1 \choose j}\right] \\ & = & \displaystyle
{n \choose 0} + \sum_{j=1}^{\lfloor \frac{n+1}{2}  \rfloor} {n-j \choose j} \\ & = & \displaystyle \sum_{j=0}^{\lfloor \frac{n+1}{2}  \rfloor} {n-j \choose j} = F_{n+1}, \end{array}$$ as we wanted to prove.