10
$\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$

1 Answer 1

5
$\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$
6
  • $\begingroup$ how do you arrive at the general identity (first expression)? $\endgroup$
    – sku
    Commented Apr 11, 2017 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$ Commented Apr 11, 2017 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
    Commented Apr 11, 2017 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$ Commented Apr 11, 2017 at 22:03
  • $\begingroup$ pluggin n = 2 in $\sum_{k=0}^{n-1} F_{k+1} \binom{n}{k} = F_{2n-1}$ $\endgroup$
    – sku
    Commented Apr 11, 2017 at 22:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .