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

  • $\begingroup$ Is induction allowed ? (The Fibonacci numbers are defined by recurrence, not combinatorially.) $\endgroup$ – Yves Daoust Apr 22 at 16:40
  • 1
    $\begingroup$ @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.) $\endgroup$ – Cheerful Parsnip Apr 22 at 16:48
  • $\begingroup$ Sure @Yves Daoust $\endgroup$ – SutMar Apr 22 at 22:56
  • $\begingroup$ @Cheerful Parsnip Could you hep me sir? :( $\endgroup$ – SutMar Apr 22 at 22:57
  • $\begingroup$ @SutMar, I don't see a good combinatorial proof but I think it's an interesting question. $\endgroup$ – 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


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

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


$$F_{2n+2} = [z^{n+1}] \frac{z}{1-3z+z^2} = [z^n] \frac{1}{1-3z+z^2}$$

as required.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.