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!

Solution 1:

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}