# 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

• Is induction allowed ? (The Fibonacci numbers are defined by recurrence, not combinatorially.) – Yves Daoust Apr 22 at 16:40
• @YvesDaoust, one could of course take a combinatorial problem for which the Fibonaccis are the answer as the basis for a combinatorial solution. (E.g. the number of ways to tile a $2\times n$ rectangle with $1\times 2$ or $2\times 1$ tiles.) – Cheerful Parsnip Apr 22 at 16:48
• Sure @Yves Daoust – SutMar Apr 22 at 22:56
• @Cheerful Parsnip Could you hep me sir? :( – SutMar Apr 22 at 22:57
• @SutMar, I don't see a good combinatorial proof but I think it's an interesting question. – Cheerful Parsnip Apr 23 at 21:43

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} \\ = \mathrm{Res}_{w=0} \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

$$\mathrm{Res}_{v=0} \frac{1}{v^{n+1}} \frac{1}{1+v/(1-2v)-v^2/(1-2v)^2} \frac{1}{(1-2v)^2} \\ = \mathrm{Res}_{v=0} \frac{1}{v^{n+1}} \frac{1}{(1-2v)^2+v(1-2v)-v^2} \\ = \mathrm{Res}_{v=0} \frac{1}{v^{n+1}} \frac{1}{1-3v+v^2}.$$

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