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.