proof verification - 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?

Answer

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.