Counting argument proof or inductive proof of $F_1 {n \choose1}+…+F_n {n \choose n} = F_{2n}$ where $F_i$ are Fibonacci

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.

• 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. – 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.

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

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}$$

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\, .$$

• That's the clearest proof! – lhf Feb 21 '18 at 10:37