Combinatorial proof of fibonacci I need to proof this expression combinatorially
$f_{2n+1}= \sum_{i \geq 0} \sum_{j\geq 0} \binom{n-i}{j} \binom{n-j}{i}$ for all $n \geq 0$. As $f_1 = 1, f_2=2$
I dont know how to start combinatorial argument to this problem .I tried to use induction but it's hard to get the inductive result
 A: We shall use tessellations of a $1 \times n$ grid with (singleton) squares and dominoes to give a combinatorial proof. But first a quick lemma.
Lemma: A $1 \times m$ grid can be tessallated with $j$ dominoes and $m-2j$ squares in $\binom{m-j}{j}$ ways. ($m \geq j$)
Proof: We will show this using a one-one correspondence. Let $ \{a_1,\cdots,a_j \} $ be a $j-$set of  $[m-j]$ (of which there are clearly $\binom{m-j}{j}$. Now place dominoes at $ a_1,a_2+1, \cdots ,a_j+j-1$ and fill the rest of the grid with squares. It is easily shown that these configurations and sets are bijective.
Now to prove the stated formula, first observe that $F_{2n+1}$ is the number of tessellations of a $1 \times (2n+1)$ grid with  squares and dominoes.
Alternatively, such a configuration will have $k$ dominoes and $2n-2k+1$ squares. Observe that there will always be an odd number of squares and we consider the position of the "middle" square. There will be $j$ dominoes to the left of this square and $i$ squares to the right. ($i+j=k$).
To the left there are $j$ dominoes and $n-k$ squares, by the lemma there are $\binom{n-i}{j}$ ways to arrange these and similarly to the right there are $i$ dominoes and $n-k$ squares, by the lemma there are $\binom{n-j}{i}$ ways to arrange these.
So
\begin{eqnarray*}
F_{2n+1} = \sum_{i=0}^{n} \sum_{j=0}^{n-i} \binom{n-i}{j} \binom{n-j}{i}.
\end{eqnarray*}
In a nut shell this formula gives the number of tessellations of a $1 \times (2n+1)$ grid graded by the number of dominoes to the left and right of the central square.
