9
$\begingroup$

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!

$\endgroup$
4
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ how do you arrive at the general identity (first expression)? $\endgroup$ – sku Apr 11 '17 at 19:00
  • $\begingroup$ 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). $\endgroup$ – Misha Lavrov Apr 11 '17 at 19:12
  • $\begingroup$ 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}$ $\endgroup$ – sku Apr 11 '17 at 21:58
  • $\begingroup$ 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. $\endgroup$ – Misha Lavrov Apr 11 '17 at 22:03
  • $\begingroup$ pluggin n = 2 in $\sum_{k=0}^{n-1} F_{k+1} \binom{n}{k} = F_{2n-1}$ $\endgroup$ – sku Apr 11 '17 at 22:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.