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.
 A: (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.
A: 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\, .
$$
A: 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}$$
