Cesaro identity for Fibonacci numbers: $ F_{2n} = \sum_{k=1}^n \binom{n}{k} F_k$ I am stuck with the identity
$$
F_{2n} = \sum_{k=1}^n \binom{n}{k} F_k,
$$
which happens to be formula 80. I am using induction, but so far without too much result.
$$
\sum_{k=1}^{n+1} \binom{n+1}{k} F_k = \\
F_{n+1} + \sum_{k=1}^n \binom{n+1}{k} F_k = \\
F_{n+1} + \sum_{k=1}^n \binom{n}{k} F_k + \sum_{k=1}^n \binom{n}{k-1}F_k =\\ F_{n+1} + F_{2n} + \sum_{k=1}^n \binom{n}{k-1}F_k,
$$ 
I am stuck with the sum $ \sum_{k=1}^n \binom{n}{k-1}F_k$, because, on the other hand 
$$
F_{n+1}+ \sum_{k=1}^n \binom{n}{k-1}F_k = F_{2n+1}
$$
Which would conclude the proof. What am I missing?
 A: Let $$X_n=\left[\matrix{F_{n+1}\cr F_{n}}\right],\qquad
A=\left[\matrix{1&1\cr 1&0}\right]$$
Then clearly $X_n=A^nX_0$ for every $n\ge 0$. Now, since $A^2=A+I$ we have
$$A^{2n}=(A+I)^n=\sum_{k=0}^n\binom{n}{k}A^k$$
Multiplying both sides by $X_0$ we get the two formulas
$$\eqalign{F_{2n+1}&=\sum_{k=0}^n\binom{n}{k}F_{k+1}\cr
F_{2n}&=\sum_{k=1}^n\binom{n}{k}F_{k}
}$$
Because $F_0=0$.
A: Thank you for the answer. I found another way to prove it. Yet, as always, more suggestions are most welcome.
$$
\sum_{k=0}^n \binom{n}{k} F_k = \sum_{k=0}^n \binom{n}{k} \frac{\alpha^k-\beta^k}{\alpha-\beta},
$$
by using Binet's formula $F_k = \frac{\alpha^k-\beta^k}{\alpha-\beta}$ (Ross Honsberger, Mathematical Gems III, p109).
Now we apply the binomial theorem for each term, which gives:
$$
\frac{1}{\alpha-\beta} ((1+\alpha)^n-(1+\beta)^n).
$$
We have to use the identities $\alpha^2=\alpha+1$, $1+\beta = \beta^2$. Thus
$$
\frac{\alpha^{2n}-\beta^{2n}}{\alpha-\beta} = F_{2n}.
$$
A: Here’s a fairly natural approach that actually gives a bit more information. Suppose that we try to prove the result by induction on $n$. It’s clearly true for $n=1$. For the induction step we might try assuming that
$$F_{2n}=\sum_{k=1}^n\binom{n}kF_k$$
and proving that
$$F_{2n+2}=\sum_{k=1}^{n+1}\binom{n+1}kF_k\;.$$
It’s usually easier to start by manipulating the more complicated side:
$$\begin{align*}
\sum_{k=1}^{n+1}\binom{n+1}kF_k&=\sum_{k=1}^n\binom{n}kF_k+\sum_{k=1}^{n+1}\binom{n}{k-1}F_k\\
&=F_{2n}+\sum_{k=0}^n\binom{n}kF_{k+1}\;,
\end{align*}$$
and we’d be in business if we knew that 
$$\sum_{k=0}^n\binom{n}kF_{k+1}=F_{2n+1}\;,$$
since $F_{2n}+F_{2n+1}=F_{2n+2}$. This suggests that we should actually try to prove both results at once. Since $F_0=0$, I can write it like this:

Theorem: For each $n\ge 0$, $$F_{2n}=\sum_{k=0}^n\binom{n}kF_k\qquad\text{and}\qquad F_{2n+1}=\sum_{k=0}^n\binom{n}kF_{k+1}\;.\tag{1}$$ 

It’s easy to verify $(1)$ for $n=0$. Assume that $(1)$ holds for some $n$. Then
$$\begin{align*}
\sum_{k=0}^{n+1}\binom{n+1}kF_k&=\sum_{k=0}^n\binom{n}kF_k+\sum_{k=1}^{n+1}\binom{n}{k-1}F_k\\
&=F_{2n}+\sum_{k=0}^n\binom{n}kF_{k+1}\\
&=F_{2n}+F_{2n+1}\\
&=F_{2n+2}\;,
\end{align*}$$
and
$$\begin{align*}
\sum_{k=0}^{n+1}\binom{n+1}kF_{k+1}&=\sum_{k=0}^n\binom{n}kF_{k+1}+\sum_{k=1}^{n+1}\binom{n}{k-1}F_{k+1}\\
&=F_{2n+1}+\sum_{k=0}^n\binom{n}kF_{k+2}\\
&=F_{2n+1}+\sum_{k=0}^n\binom{n}k(F_{k+1}+F_k)\\
&=F_{2n+1}+\left(\sum_{k=0}^n\binom{n}kF_{k+1}+\sum_{k=0}^n\binom{n}kF_k\right)\\
&=F_{2n+1}+(F_{2n+1}+F_{2n})\\
&=F_{2n+1}+F_{2n+2}\\
&=F_{2n+3}\;,
\end{align*}$$
as desired. The theorem now follows by induction.
