# Binomial coefficient and fibonacci numbers

I found the following problem in putnam and beyond: prove that $$F_{2n} = \sum_{k=1}^{n} F_{k}{{n}\choose {k}}$$

The answer in the back of the book uses the closed form of $F_n$, but it seems to me their should be a solution using only the properties of the binomial cooeficient. I tried using $${{n} \choose {k}} = {{n-1} \choose {k}}+ {{n-1}\choose {k-1}}$$

but this seems to be a dead end, and I have no other ideas.

Any help is appreciated!

Before we can prove it by applying Pascal's identity and the Fibonacci recurrence, we must generalize the identity to $$F_{2n+m} = \sum_{k=0}^n F_{k+m} \binom{n}{k}.$$
Now we can proceed by induction on $n$. When $n=0$, the identity just says $F_m = F_m$, and that will be our base case. For $n>0$, we have: \begin{align} \sum_{k=0}^n F_{k+m} \binom{n}{k} &= \sum_{k=0}^n F_{k+m} \binom{n-1}{k-1} + \sum_{k=0}^n F_{k+m} \binom{n-1}{k} \\ &= \sum_{k=0}^{n-1} F_{k+m+1} \binom{n-1}{k} + \sum_{k=0}^{n-1} F_{k+m} \binom{n-1}{k} \\ &= F_{2(n-1)+m+1} + F_{2(n-1)+m} \\ &= F_{2n+m}. \end{align}
• The original identity is the $m=0$ case. If you try to prove the original identity by induction, you find that it requires $\sum_{k=0}^{n-1} F_{k+1} \binom{n}{k} = F_{2n-1}$ to hold, which is the $m=1$ case. So you might already guess from there that the identity holds for all $m$ (or notice that if it holds for $m=0$ and $m=1$, then it must hold for $m=2,3,\dots$ due to the Fibonacci recurrence). – Misha Lavrov Apr 11 '17 at 19:12
• Something seems amiss to me. Take n = 2. We get $F_3 = F_1\binom{2}{0} + F_2\binom{2}{1} = F_1 + 2F_2$. I think the correct expression should be F_{2n+1} = \sum_{1}^{n+1}F_k\binom{n}{k-1}$– sku Apr 11 '17 at 21:58 • What are you plugging into which identity to get$F_3 = F_1 \binom20 + F_2 \binom21$? The identity with$m=0$can't give$F_3$, since it equals$F_{2n}$, and you haven't said what$m$is. – Misha Lavrov Apr 11 '17 at 22:03 • pluggin n = 2 in$\sum_{k=0}^{n-1} F_{k+1} \binom{n}{k} = F_{2n-1}\$ – sku Apr 11 '17 at 22:04