Prove: $\binom{n}{0}F_0+\binom{n}{1}F_1+\binom{n}{2}F_2+\cdots+\binom{n}{n}F_n=F_{2n}$ Prove: $\binom{n}{0}F_0+\binom{n}{1}F_1+\binom{n}{2}F_2+\cdots+\binom{n}{n}F_n=F_{2n}$; 
I was stuck with this question for a while... Help me please!!! Thanks!!!
 A: 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} $$

A: 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]$
A: 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$$
