# Fibonacci combinatorial identity

Can someone explain how to prove the following identity involving Fibonacci sequence $F_n$

$F_{2n} = {n \choose 0} F_0 + {n\choose 1} F_1 + ... {n\choose n} F_n$ ?

-
Symbolically, this is similar to $${2n\choose n}={n\choose 0}\cdot{n\choose 0}+{n\choose 1}\cdot{n\choose 1}+\ldots+{n\choose n}\cdot{n\choose n}$$ – Lucian Nov 17 '13 at 9:40

Let $\alpha:=\displaystyle\frac{1+\sqrt5}2$ and $\beta:=\displaystyle\frac{1-\sqrt5}2$, then we have $$F_n=\frac{\alpha^n-\beta^n}{\sqrt5}\,.$$ Using this, $$\sum_{k\le n}\binom nk F_k=\frac1{\sqrt5}\left((1+\alpha)^n -(1+\beta)^n\right)\,.$$ Now $1+\alpha=\displaystyle\frac{3+\sqrt5}2=\alpha^2$ and similarly, $1+\beta=\beta^2$. (These were just the solutions of $x^2=x+1$.)
Recall that $F_{2n+1}$ is the number of ways to tile a $1\times2n$-rectangle with squares and dominoes.
Let's focus on first $n$ tiles. We can choose which of them are squares in $\binom ni$ ways and the rest $(2n+1)-i-2(n-i)=i+1$ cells can be tiled in $F_i$ ways.