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

Question

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.

Answer 1

(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.

Answer 2

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

Answer 3

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