Prove that $$F_1 {n\choose1} +...+F_n {n\choose n} = F_{2n}$$ where $F_i$ is the $i$th Fibonacci number.

This question is mentioned on Putnam and Beyond book number 861. I looked at the proof of the question, and the book's proof uses Binet's formula (i.e. the explicit formula for $n$th Fibonacci number), binomial formula, and the fact that $\frac{3+\sqrt{5}}{2} = (\frac{1+\sqrt{5}}{2})^2$. I am wondering whether there is a counting argument for this proof (or an inductive proof), and if so, it would be great if anyone posts them here.

  • $\begingroup$ You can also write $n$ choose $k$ as follows: $$\binom nk$$ which is \binom nk with dollar signs at the beginning and end, or n\choose k with dollar signs etc. $\endgroup$
    – Mr Pie
    Jan 14 '18 at 7:41

(The following answer is essentially Example 3.1.5 in this pdf.)

First, $F_{2n}$ counts the number of ways of tiling a strip of length $2n-1$ with tiles of length either $1$ (squares) or $2$ (dominos).

Now, let's look at the number of tilings of that strip in which $k$ of the first $n$ tiles are squares. There are $\binom{n}{k}$ ways of arranging the first $n$ tiles. A collection of $k$ squares and $n-k$ dominos will have length $2n-k$. So the strip remaining after the first $n$ tiles has length $k-1$, which means that it can be tiled in $F_k$ ways. In summary, the number of tilings of this sort is $F_k \binom{n}{k}$.

Moreover any tiling of the strip uses at least $n$ tiles (or it would have length at most $2n-2$), and the first $n$ tiles cannot all be dominos (or they would have length $2n$). So we have $$ F_{2n}=\sum_{k=1}^n F_n \binom{n}{k} $$ as desired.

  • $\begingroup$ Note that this proof also can be easily adapted to give the more general identity in @achille hui's answer. $\endgroup$
    – Micah
    Jan 14 '18 at 14:50

Although this not my answer, I would like to rewrite it here. In fact, every time I read the @Robert Israel answer I understand that I know a bit about Fibonacci numbers and not more!

Consider $A=\pmatrix{0 & 1\cr 1 & 1\cr}$ then the $n$th power of $A$, denoted by $A^n$, is obtained as follows $$ A^n = \pmatrix{F_{n-1} & F_{n}\cr F_n & F_{n+1}} . $$ where $F_n$ is the $n$th term of Fibonacci numbers. The matrix $A$ is satisfaied on the equation $x^2-x-1=0$, since we have $$ \pmatrix{1 & 1\cr 1 & 2\cr}=\pmatrix{0 & 1\cr 1 & 1\cr}+\pmatrix{1 & 0\cr 0 & 1\cr} \Leftrightarrow A^2=A+I $$ Therefore, we get $$ A^{2n}=(A^2)^n=(A+I)^n=\sum_{j=0}^n C_j^n\, A^j \tag{1} $$ Now consider the entry of the first row and second column of the matrix equation $(1)$ which impliying that $$ F_{2n}=\sum_{j=0}^n C_j^n\, F_j\, . $$

  • 1
    $\begingroup$ That's the clearest proof! $\endgroup$
    – lhf
    Feb 21 '18 at 10:37

This is one way to attack the problem by induction. We need to generalize the statement a little bit before we can carry out the induction step.

Extend definition of $F_n$ to $F_0 = 0$. For any $n > 0$, let $\mathcal{S}_n$ be the statement:

$$\mathcal{S}_n :\quad F_{2n+k} = \sum_{\ell=0}^n \binom{n}{\ell} F_{\ell+k},\;\text{ for all k} \ge 0$$ When $n = 1$, $S_n$ reduces to $F_{k+2} = F_{k+1} + F_k$ for all $k \ge 0$. This is trivially true.

Assume $\mathcal{S}_{n}$ is true. For any $k \ge 0$, we have

$$\begin{align}F_{2(n+1)+k} = F_{2n+(k+2)} &\stackrel{\mathcal{S}_n}{=} \sum_{\ell=0}^n \binom{n}{\ell} F_{\ell+(k+2)} = \sum_{\ell=0}^n \binom{n}{\ell} \left( F_{\ell+k+1} + F_{\ell+k}\right)\\ &= \sum_{\ell=1}^{n+1}\binom{n}{\ell-1}F_{\ell+k} + \sum_{\ell=0}^n \binom{n}{\ell} F_{\ell+k}\\ &= F_{n+1+k} + F_k + \sum_{\ell=1}^n \left(\binom{n}{\ell-1}+\binom{n}{\ell}\right)F_{\ell+k} \end{align} $$ Notice $\binom{n+1}{\ell} = \binom{n}{\ell}+\binom{n}{\ell-1}$ for $1 \le \ell \le n$, this leads to $$F_{2(n+1)+k} = F_{n+1+k} + F_{k} + \sum_{\ell=1}^n \binom{n+1}{\ell}F_{\ell+k} = \sum_{\ell=0}^{n+1} \binom{n+1}{\ell}F_{\ell+k}$$ Since this is valid for all $k$, $\mathcal{S}_{n+1}$ is true. By principle of induction $\mathcal{S}_n$ is true for all $n$.
In particular, if we fix $k$ to $0$, the desired identity follows: $$F_{2n} = \sum_{\ell=0}^n \binom{n}{\ell}F_{\ell} = \sum_{\ell=1}^n \binom{n}{\ell}F_{\ell}$$


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.