Inductive proof of the identity $\binom{n} {0} F_0+\binom{n}{1} F_1+\binom{n}{2} F_2+\cdots +\binom{n}{n} F_n=F_{2n}$

Question

I'm trying to prove the following identity:
$$\binom{n} {0} F_0+\binom{n}{1} F_1+\binom{n}{2} F_2+\cdots +\binom{n}{n} F_n=F_{2n}$$

I need to prove it using induction (not a counting argument), I know simultaneous induction has to be used but other than that I'm totally lost.

Answer 1

The case for $F_0$ is trivial. For the inductive step, based on the assumption that: $\displaystyle \sum_{r=0}^{k} \binom{k}{r} F_r = F_{2k}$, we get the following (using Pascal's Rule, Binet's formula and the Binomial Theorem): $$ \sum_{r=0}^{k+1} \binom{k+1}{r} F_r = \sum_{r=1}^{k} \left(\binom{k}{r}+ \binom{k}{r-1}\right) F_r + F_0 + F_{k+1} = \sum_{r=0}^{k} \binom{k}{r} F_r + \sum_{r=1}^{k} \binom{k}{r-1}F_r + F_{k+1}=F_{2k}+\sum_{r=0}^{k} \binom{k}{r} F_{r+1} = F_{2k}+\sum_{r=0}^{k} \binom{k}{r} \left(\frac{\varphi^{r+1}-\psi^{r+1}}{\sqrt{5}}\right) = F_{2k}+\frac1{\sqrt{5}}\sum_{r=0}^{k} \binom{k}{r} (\varphi^{r+1}-\psi^{r+1}) =F_{2k}+\frac1{\sqrt{5}}\left(\varphi\sum_{r=0}^{k} \binom{k}{r} \varphi^{r}-\psi\sum_{r=0}^{k} \binom{k}{r}\psi^{r}\right) =F_{2k}+\frac1{\sqrt{5}}\left(\varphi(1+\varphi)^k-\psi(1+\psi)^k\right)=F_{2k}+\frac1{\sqrt{5}}\left(\varphi(\varphi^2)^k-\psi(\psi^2)^k\right)=F_{2k}+F_{2k+1}=F_{2k+2} $$ (NB: $\displaystyle\varphi = \frac{1+\sqrt{5}}{2}, \psi = \frac{1-\sqrt{5}}{2}$)

Answer 2

Let's try to work out induction in reverse. Suppose that we already have $$F_{2n}=\binom{n}{0}F_0+\binom{n}{1}F_1+\cdots+\binom{n}{n}F_n\tag{1},$$ and we want to show $$F_{2n+2}=\binom{n+1}{0}F_0+\binom{n+1}{1}+\cdots +\binom{n+1}{n+1}F_{n+1}\tag{2}.$$ Compare (1) and (2) we want to prove $$F_{2n+1}=\left(\binom{n+1}{0}-\binom{n}{0}\right) F_0+\left(\binom{n+1}{1}-\binom{n}{1}\right)F_1+\cdots+\left(\binom{n+1}{n}-\binom{n}{n}\right)F_n+F_{n+1},$$ or $$F_{2n+1}=\binom{n}{0}F_1+\cdots+\binom{n}{n-1}F_n+\binom{n}{n}F_{n+1}\tag{3}.$$ Given (1), Equality (3) is true if $$F_{2n-1}=\binom{n}{0}(F_1-F_0)+\binom{n}{1}(F_2-F_1)+\cdots+\binom{n}{n-1}(F_n-F_{n-1})+\binom{n}{n}(F_{n+1}-F_{n})$$ or if $$\begin{aligned}F_{2n-1}&=\binom{n}{1}F_0+\cdots+\binom{n}{n-1}F_{n-2}+\binom{n}{n}F_{n-1}\\ &=\left(\binom{n-1}{0}+\binom{n-1}{1}\right)F_0+\left(\binom{n-1}{1}+\binom{n-1}{2}\right)F_1+\cdots\\ &+\left(\binom{n-1}{n-1}+\binom{n-1}{n-2}\right)F_{n-2}+\binom{n-1}{n-1}F_{n-1} .\end{aligned}$$ Regrouping terms, the last equality becomes (note $F_0=F_1=1$) $$F_{2n-1}=\binom{n-1}{0}F_1+\cdots+\binom{n-1}{n-1}F_n.\tag{4}$$

---

Here we see that Equality (4) is Equality (3) for $n-1$. That suggests we should perform induction simultaneously on (1) and (4). And of course, the actual proof is the reverse of the above.