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
On
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.
What follows is not a double counting proof. It nonetheless uses combinatorial methods to arrive at the answer.
Observe that the generating function of the Fibonacci numbers is
$$\frac{z}{1-z-z^2}.$$
so that we have $F_0 = 0$ and $F_1 = F_2 = 1.$
We seek to evaluate
$$\sum_{p=0}^n \sum_{q=0}^n {n-p\choose q} {n-q\choose p} \\ = \sum_{p=0}^n \sum_{q=0}^n {n-p\choose n-p-q} {n-q\choose n-p-q}.$$
Note that on the first line the binomial coefficient ${n\choose k} = n^{\underline{k}}/{k!}$ starts producing non-zero values when $p\gt n$ and $q\gt n.$ This is not desired here, hence the upper limits. On the second line we use the convention that ${n\choose k} = 0$ when $k\lt 0,$ which is also the behavior when residues are used. Continuing we find
$$\sum_{p=0}^n \sum_{q=0}^n [z^{n-p-q}] (1+z)^{n-p} [w^{n-p-q}] (1+w)^{n-q} \\ = [z^n] (1+z)^n [w^n] (1+w)^n \sum_{p=0}^n \sum_{q=0}^n z^{p+q} (1+z)^{-p} w^{p+q} (1+w)^{-q} \\ = [z^n] (1+z)^n [w^n] (1+w)^n \sum_{p=0}^n z^p w^p (1+z)^{-p} \sum_{q=0}^n z^q w^q (1+w)^{-q}.$$
Here the coefficient extractor controls the range and we may continue with
$$[z^n] (1+z)^n [w^n] (1+w)^n \sum_{p\ge 0} z^p w^p (1+z)^{-p} \sum_{q\ge 0} z^q w^q (1+w)^{-q} \\ = [z^n] (1+z)^n [w^n] (1+w)^n \frac{1}{1-zw/(1+z)} \frac{1}{1-zw/(1+w)} \\ = [z^n] (1+z)^{n+1} [w^n] (1+w)^{n+1} \frac{1}{1+z-zw} \frac{1}{1+w-zw}.$$
Now we have
$$\frac{1}{1+z-zw} \frac{1}{1+w-zw} \\ = \frac{1-w}{1+z-wz} \frac{1}{1+w-w^2} + \frac{w}{1+w-wz} \frac{1}{1+w-w^2}.$$
We get from the first piece treating $z$ first
$$[z^n] (1+z)^{n+1} \frac{1-w}{1+z-wz} = [z^n] (1+z)^{n+1} \frac{1-w}{1-z(w-1)} \\ = (1-w) \sum_{p=0}^n {n+1\choose n-p} (w-1)^p = - \sum_{p=0}^n {n+1\choose p+1} (w-1)^{p+1} \\ = 1 - \sum_{p=-1}^n {n+1\choose p+1} (w-1)^{p+1} = 1 - w^{n+1}.$$
The contribution is
$$[w^n] (1+w)^{n+1} \frac{1-w^{n+1}}{1+w-w^2} = [w^n] (1+w)^{n+1} \frac{1}{1+w-w^2}.$$
The second piece yields
$$[z^n] (1+z)^{n+1} \frac{w}{1+w-wz} = \frac{1}{1+w} [z^n] (1+z)^{n+1} \frac{w}{1-wz/(1+w)} \\ = \frac{w}{1+w} \sum_{p=0}^n {n+1\choose n-p} \frac{w^p}{(1+w)^p} = \sum_{p=0}^n {n+1\choose p+1} \frac{w^{p+1}}{(1+w)^{p+1}} \\ = -1 + \sum_{p=-1}^n {n+1\choose p+1} \frac{w^{p+1}}{(1+w)^{p+1}} = -1 + \left(1+\frac{w}{1+w}\right)^{n+1} \\ = -1 + \frac{(1+2w)^{n+1}}{(1+w)^{n+1}}.$$
The contribution is
$$[w^n] (1+w)^{n+1} \left(-1 + \frac{(1+2w)^{n+1}}{(1+w)^{n+1}}\right) \frac{1}{1+w-w^2}.$$
Adding the first and the second contribution we find
$$[w^n] (1+2w)^{n+1} \frac{1}{1+w-w^2} \\ = \underset{w}{\mathrm{res}}\; \frac{1}{w^{n+1}} (1+2w)^{n+1} \frac{1}{1+w-w^2}.$$
Setting $w/(1+2w)=v$ or $w=v/(1-2v)$ so that $dw = 1/(1-2v)^2 \; dv$ we obtain
$$\underset{v}{\mathrm{res}}\; \frac{1}{v^{n+1}} \frac{1}{1+v/(1-2v)-v^2/(1-2v)^2} \frac{1}{(1-2v)^2} \\ = \underset{v}{\mathrm{res}}\; \frac{1}{v^{n+1}} \frac{1}{(1-2v)^2+v(1-2v)-v^2} \\ = \underset{v}{\mathrm{res}}\; \frac{1}{v^{n+1}} \frac{1}{1-3v+v^2}.$$
We have our answer:
$$\bbox[5px,border:2px solid #00A000]{ [v^n] \frac{1}{1-3v+v^2} = F_{2n+2}.}$$
It remains to prove that the coefficient extractor returns the Fibonacci number as claimed. The OGF of even-index Fibonacci numbers is
$$\sum_{n\ge 0} F_{2n} z^{2n} = \frac{1}{2} \frac{z}{1-z-z^2} + \frac{1}{2} \frac{(-z)}{1+z-z^2} = \frac{z^2}{1-3z^2+z^4}.$$
This implies that
$$\sum_{n\ge 0} F_{2n} z^{n} = \frac{z}{1-3z+z^2}.$$
Therefore
$$F_{2n+2} = [z^{n+1}] \frac{z}{1-3z+z^2} = [z^n] \frac{1}{1-3z+z^2}$$
as required.