Prove: $\binom{n}{0}F_0+\binom{n}{1}F_1+\binom{n}{2}F_2+\cdots+\binom{n}{n}F_n=F_{2n}$

Solution 1:

A counting argument:

The number of ways of climbing $n$ stairs, taking $1$ or $2$ steps at a time is $F_n$ (Try proving it).

Now suppose we had to climb $2n$ stairs. Note that we need to take at least $n$ moves.

We now consider the position after taking exactly $n$ moves. For each such position, we consider where we are and how many ways we can cover the rest.

This we do by considering the number of steps of $2$ we take.

If we take $k$ steps of $2$, then we take $n-k$ steps of $1$ for the first $n$ moves. We end up at step $n+k$, thus leaving $n-k$ steps to cover. These $n-k$ steps can be covered in $F_{n-k}$ ways and the number of ways of getting there is same as the number of ways of choosing $k$ moves of $2$ from $n$, which is $\binom{n}{k}$.

Thus as $k$ ranges from $0$ to $n$, we have that the number of ways of covering $2n$ stairs is

$$F_{2n} = \sum_{k=0}^{n} \binom{n}{k} F_{n-k}$$

Since $\binom{n}{k} = \binom{n}{n-k}$ we get

$$ \binom{n}{0}F_0 + \binom{n}{1}F_1 + \dots + \binom{n}{n}F_n = F_{2n}$$

A simple generalization of this argument gives us, for $2n \le m$

$$ \binom{n}{0} F_{m-2n} + \binom{n}{1} F_{m-2n+1} + \dots + \binom{n}{n} F_{m-n} = F_m$$

Solution 2:

Hint: Binet's formula + Binomial formula. Also, $\varphi^2=\varphi+1$ and $\varphi^{-2}=2-\varphi$.

$$\hskip 1.5in \displaystyle \sum_{\ell=0}^n \binom{n}{\ell}\frac{\varphi^\ell-(1-\varphi)^\ell}{\sqrt5}=\frac{(1+\varphi)^{\ell}-(2-\varphi)^\ell}{\sqrt5}=F_{2n} $$

Solution 3:

I accidentally stumbled across this old question while studying some facts about generating functions and could not resist posting this answer. Take an ordinary generating function of the LHS: $$G(x)=\sum_{n\ge0}\sum_{0\le k\le n}\left(\begin{array}{c} n\\ k \end{array}\right)F_kx^n$$ Change the order of summation to obtain

$$G(x)=\sum_{k\ge0}\sum_{n\ge k}\left(\begin{array}{c} n\\ k \end{array}\right)F_kx^n=\sum_{k\ge0}F_k\sum_{n\ge0}\left(\begin{array}{c} n+k\\ k \end{array}\right)x^{n+k}\\=\sum_{k\ge0}F_kx^k\sum_{n\ge0}\left(\begin{array}{c} n+k\\ n \end{array}\right)x^n=\sum_{k\ge0}F_kx^k\frac{1}{\left(1-x\right)^{1+k}}\\=\frac{1}{1-x}\sum_{k\ge0}F_k\left(\frac{x}{1-x}\right)^k$$ Now the expression under the sum is just the ordinary generating $F(z)$function for $F_n$ $$F(z)=\frac{z}{1-z-z^2}$$ where $z=\frac{x}{1-x}$. Substituting we obtain $$G(x)=\frac{x}{1-3x-x^2}$$ The last expression is the generating function for $F_{2n}$ as can be ascertained by calculating $\frac{1}{2}\left[F(x)+F(-x)\right]$