# Binomial Sum Related to Fibonacci: $\sum\binom{n-i}j\binom{n-j}i=F_{2n+1}$

How would I prove

$$\sum\limits_{\vphantom{\large A}i\,,\,j\ \geq\ 0}{n-i \choose j} {n-j \choose i} =F_{2n+1}$$

where $n$ is a nonnegative integer and $\{F_n\}_{n\ge 0}$ is a sequence of Fibonacci numbers?

Thank you very much! :)

• Try a combinatorial proof - can you associate a quantity to be counted with each term in the sum? – Batman May 19 '14 at 16:37
• Any idea? I've tried to associate them with binary string, tiling of 1 x n board, and even try to find its generating function, but no result. :( – Yozef Tjandra May 19 '14 at 16:48

## 6 Answers

### Combinatorial proof 1

$F_{2n+1}$ is the number of tiling of an $1\times(2n+1)$-rectangle by squares and dominoes. Any such tiling contains an odd number of squares, so we can find the middle square. The number of such tilings with $i$ dominoes to the left of this square and $j$ to the right (and $n-i-j$ squares in both parts) is exactly $\binom{n-j}{i\vphantom j}\binom{n-i}j$.

(Cf. combinatorial proof of $F_n=\sum\binom{n-i}i$.)

### Combinatorial proof 2

$F_{2n+1}$ is the number of 00-avoiding binary sequences of length $2n$. Claim: there are $\binom{n-j}i\binom{n-i}j$ such sequence with $i$ zeroes at odd places and $j$ zeroes at even places.

(Indeed, take a sequence of length $n-j$ with $i$ zeroes and a sequence of length $n-i$ with $j$ zeroes; write the first element of the first sequence; if it's 0 is should be followed by 1, otherwise use the first element of the second sequence — and so on; in the end you'll get a 00-avoiding sequence of length exactly $2n$.)

P.S. The last proof can be adapted to show that $$2\sum\binom{n-k}i\binom{n-i}j\binom{n-j}k=F_{3n+2}$$ and so on. Details can be found in A. Benjamin, J. Rouse, 'Recounting Binomial Fibonacci Identities', Applications of Fibonacci Numbers, Volume 9 (2003).

P.P.S. If you prefer convention where $F_0=0$ (instead of $F_0=1$), read $F_{2n+2}$ instead of $F_{2n+1}$ etc everywhere starting from the question.

• – Grigory M Jan 5 '15 at 21:19

The problem asks to show that \begin{align} \sum_{i=0}^{n} \sum_{j=0}^{n} \binom{n-i}{j} \binom{n-j}{i} = F_{2n+1}. \end{align} The problem, as stated, is incorrect. It should read $F_{2n+2}$. This will be shown in the following.

Consider the double summation \begin{align} S_{n} = \sum_{i=0}^{n} \sum_{j=0}^{n} \binom{n-i}{j} \binom{n-j}{i}. \end{align} By reversing the summation over the index $i$ this becomes \begin{align} S_{n} = \sum_{i=0}^{n} \sum_{j=0}^{i} \binom{i}{j} \binom{n-j}{n-i}. \end{align} Now consider the generating function of $S_{n}$. \begin{align} \sum_{n=0}^{\infty} S_{n} t^{n} &= \sum_{n=0}^{\infty} \sum_{i=0}^{n} \sum_{j=0}^{i} \binom{i}{j} \binom{n-j}{n-i} \ t^{n} \\ &= \sum_{n=0}^{\infty} \sum_{i=0}^{\infty} \sum_{j=0}^{i} \binom{i}{j} \binom{n+i-j}{n} \ t^{n+i} \\ &= \sum_{i=0}^{\infty} \sum_{j=0}^{i} \binom{i}{j} \ t^{i} \cdot \sum_{n=0}^{\infty} \binom{n+i-j}{n} \ t^{n} \\ &= \sum_{i=0}^{\infty} \sum_{j=0}^{i} \binom{i}{j} \ t^{i} \ (1-t)^{-i+j-1} \\ &= \frac{1}{1-t} \ \sum_{i=0}^{\infty} \left( \frac{t}{1-t} \right)^{i} \cdot \sum_{j=0}^{i} \binom{i}{j} \ (1-t)^{j} \\ &= \frac{1}{1-t} \ \sum_{i=0}^{\infty} \left( \frac{t}{1-t} \right)^{i} \ (2-t)^{i} \\ &= \frac{1}{1-t} \ \sum_{i=0}^{\infty} \left( \frac{2t - t^{2}}{1-t} \right)^{i} \\ &= \frac{1}{1-t} \ \frac{1-t}{1-3t+t^{2}} \\ &= \frac{1}{1-3t+t^{2}}. \end{align} Now, \begin{align} \frac{1}{1-3t+t^{2}} &= \frac{1-t}{1-3t+t^{2}} + \frac{t}{1-3t+t^{2}} \\ &= \sum_{n=0}^{\infty} F_{2n+1} \ t^{n} + \sum_{n=0}^{\infty} F_{2n} \ t^{n} \\ &= \sum_{n=0}^{\infty} F_{2n+2} \ t^{n} \end{align} which, when compared to the previous result, leads to \begin{align} \sum_{i=0}^{n} \sum_{j=0}^{n} \binom{n-i}{j} \binom{n-j}{i} = F_{2n+2}. \end{align}

One more proof. Let's rewrite the sum in terms of $i$ and $k=i+j$: $$\binom{n-i}j\binom{n-j}i=\binom{n-i}{n-k}\binom{n-k+i}{n-k}.$$ Vandermonde convolution implies $$\sum_i\binom{n-i}{n-k}\binom{n-k+i}{n-k}=\binom{2n+1-k}{2n+1-2k};$$ Now we only need to use well-known fact $$\sum_k\binom{2n+1-k}{2n+1-2k}=F_{2n+1}.$$

If $S$ is the shift operator and $F$ is the Fibonacci sequence, then $(S^2-S-1)F=0$. Thus, \begin{align} (S^4-3S^2+1)F &=(S^2+S-1)(S^2-S-1)F\\ &=(S^2+S-1)\,0\\ &=0\tag{1} \end{align} Therefore, the Fibonacci sequence also satisfies $$F_{2n+2}=3F_{2n}-F_{2n-2}\tag{2}$$

Let $$f(n)=\sum_{i,j\ge0}^n\binom{n-i}{j}\binom{n-j}{i}\tag{3}$$ Substituting $i\mapsto i-1$ and $j\mapsto j-1$ gives \begin{align} f(n-1) &=\sum_{i,j\ge0}^{n-1}\binom{n-1-i}{j}\binom{n-1-j}{i}\\ &=\sum_{i,j\ge1}^n\binom{n-i}{j-1}\binom{n-j}{i-1}\tag{4} \end{align} The definition of Pascal's Triangle, $(3)$, and $(4)$ yield \begin{align} &f(n+1)\\[9pt] &=\sum_{i,j\ge0}^n\binom{n+1-i}{j}\binom{n+1-j}{i}\\ &=\sum_{i,j\ge0}^n\left[\binom{n-i}{j}+\binom{n-i}{j-1}\right]\left[\binom{n-j}{i}+\binom{n-j}{i-1}\right]\\ &=\sum_{i,j\ge0}^n\color{#C00000}{\binom{n-i}{j}\binom{n-j}{i}}+\color{#00A000}{\binom{n-i}{j-1}^n\binom{n-j}{i}}\\ &+\sum_{i,j\ge0}^n\color{#00A000}{\binom{n-i}{j}\binom{n-j}{i-1}}+\color{#0000FF}{\binom{n-i}{j-1}\binom{n-j}{i-1}}\\ &=\color{#C00000}{f(n)}+\color{#0000FF}{f(n-1)}+\color{#00A000}{2}\sum_{i,j\ge0}^n\color{#00A000}{\binom{n-i}{j}\binom{n-1-j}{i}}\\ &=f(n)+f(n-1)+2\sum_{i,j\ge0}^n\binom{n-i}{j}\left[\binom{n-j}{i}-\binom{n-1-j}{i-1}\right]\\ &=f(n)+f(n-1)+2\sum_{i,j\ge0}^n\left[\binom{n-i}{j}\binom{n-j}{i}-\binom{n-i}{j}\binom{n-1-j}{i-1}\right]\\ &=f(n)+f(n-1)+2\sum_{i,j\ge0}^n\left[\color{#C00000}{\binom{n-i}{j}\binom{n-j}{i}}-\color{#0000FF}{\binom{n-i}{j-1}\binom{n-j}{i-1}}\right]\\[6pt] &=f(n)+f(n-1)+2[\color{#C00000}{f(n)}-\color{#0000FF}{f(n-1)}]\\[18pt] &=3f(n)-f(n-1)\tag{5} \end{align} Recursions $(2)$ and $(5)$ and the initial conditions $f(0)=1$ and $f(1)=3$ imply that $$f(n)=F_{2n+2}\tag{6}$$

• @FelixMarin: The upper limit of summation was supposed to be $n$ (or $n-1$ in places). – robjohn Jan 6 '15 at 3:04
• Sorry: You are right.I got $\displaystyle F_{2n + 2}$ by adding all terms with $\displaystyle j,k \in \left\{\,0,1,2,3,\ldots\,\right\}$ "up to $\displaystyle +\infty$". Thanks. – Felix Marin Jan 6 '15 at 5:08

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\dsc}[1]{\displaystyle{\color{red}{#1}}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,{\rm Li}_{#1}} \newcommand{\norm}[1]{\left\vert\left\vert\, #1\,\right\vert\right\vert} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ $\ds{\sum_{\vphantom{\large A}k,\,j\ \geq\ 0}{n - k \choose j}{n - j \choose k} =F_{2n + 2}:\ {\large ?}}$ where $\ds{F_{m}}$ is a Fibonacci Number.

\begin{align}&\color{#66f}{\large% \sum_{\vphantom{\large A}k,\,j\ \geq\ 0}{n - k \choose j}{n - j \choose k}} =\sum_{\vphantom{\large A}k\,,\,j\ \geq\ 0}{n - k \choose j} \oint_{\verts{z}\ =\ \varphi^{+}}{\pars{1 + z}^{n - j} \over z^{k + 1}}\,{\dd z \over 2\pi\ic} \end{align}

where $\ds{\varphi \equiv {1 + \root{5} \over 2}}$ is the Golden Ratio. Then,

\begin{align}&\color{#66f}{\large% \sum_{\vphantom{\large A}k,\,j\ \geq\ 0}{n - k \choose j}{n - j \choose k}} =\oint_{\verts{z}\ =\ \varphi^{+}}{\pars{1 + z}^{n} \over z} \sum_{k\ =\ 0}^{\infty}{1 \over z^{k}}\ \overbrace{% \sum_{j\ =\ 0}^{\infty}{n - k \choose j}\pars{1 \over 1 + z}^{j}} ^{\dsc{\pars{2 + z \over 1 + z}^{n - k}}}\,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ \varphi^{+}}{\pars{2 + z}^{n} \over z} \sum_{k\ =\ 0}^{\infty}\bracks{1 + z \over z\pars{2 + z}}^{k} \,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ \varphi^{+}}{\pars{2 + z}^{n} \over z} {1 \over 1 - \pars{1 + z}/\bracks{z\pars{2 + z}}} \,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ \varphi^{+}}{\pars{2 + z}^{n + 1} \over z^{2} + z - 1} \,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ \varphi^{+}} {\pars{2 + z}^{n + 1} \over \pars{z + \varphi}\pars{z - \varphi^{-1}}} \,{\dd z \over 2\pi\ic} ={\pars{2 - \varphi}^{n + 1} \over -\varphi - \varphi^{-1}} +{\pars{2 + \varphi^{-1}}^{n + 1} \over \varphi^{-1} + \varphi} \\[5mm]&={\pars{2 + \varphi^{-1}}^{n + 1} - \pars{2 - \varphi}^{n + 1}\over \root{5}}\quad\mbox{because}\quad \varphi^{-1} + \varphi=\root{5} \end{align}

Moreover

$$\root{2 + \varphi^{-1}}=\varphi\quad\mbox{and}\quad \root{2 - \varphi}=\varphi^{-1}$$

such that

\begin{align}&\color{#66f}{\large% \sum_{\vphantom{\large A}k,\,j\ \geq\ 0}{n - k \choose j}{n - j \choose k}} ={\varphi^{2n + 2} - \pars{-\varphi}^{-2n - 2} \over \root{5}} =\color{#66f}{\large F_{2n + 2}} \end{align}

Here is a solution using two complex variables.

Suppose we seek to evaluate in terms of Fibonacci numbers $$\sum_{p,q\ge 0} {n-p\choose q} {n-q\choose p}.$$

We use the integrals $${n-p\choose q} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{(1-z)^{q+1} z^{n-p-q+1}} \; dz$$

and $${n-q\choose p} = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{(1-w)^{p+1} w^{n-p-q+1}} \; dw.$$

These correctly control the range so we may let $p$ and $q$ go to infinity to get for the sum

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{(1-z) z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{(1-w) w^{n+1}} \sum_{p,q\ge 0} \frac{z^{p+q} w^{p+q}}{(1-w)^p (1-z)^q} \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{(1-z) z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{(1-w) w^{n+1}} \\ \times \frac{1}{1-zw/(1-w)} \frac{1}{1-zw/(1-z)} \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{n+1}} \frac{1}{1-w-zw} \frac{1}{1-z-zw} \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+2} (1+z)} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{n+1}} \frac{1}{w-1/(1+z)} \frac{1}{w-(1-z)/z} \; dw \; dz.$$

We evaluate the inner integral using the fact that the residues of the function in $w$ sum to zero. We have two simple poles. We get for the first pole at $w=(1-z)/z$ $$\frac{z^{n+1}}{(1-z)^{n+1}} \frac{1}{(1-z)/z-1/(1+z)} = \frac{z^{n+1}}{(1-z)^{n+1}} \frac{z(1+z)}{(1-z)(1+z)-z} \\ = \frac{z^{n+2}}{(1-z)^{n+1}} \frac{1+z}{(1-z)(1+z)-z}.$$

Substituting this expression into the outer integral we see that the pole at $z=0$ is canceled making for a contribution of zero.

For the second pole at $w=1/(1+z)$ we get $$(1+z)^{n+1} \frac{1}{1/(1+z)-(1-z)/z} = (1+z)^{n+1} \frac{z(1+z)}{z-(1-z)(1+z)}.$$

This yields the contribution (taking into account the sign flip from the sum of residues)

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+2} (1+z)} (1+z)^{n+1} \frac{z(1+z)}{1-z-z^2} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{n+1} \frac{1}{1-z-z^2} \; dz.$$

We evaluate this using again the fact that the residues sum to zero. There are simple poles at $z=-\varphi$ and $z=1/\varphi.$

These yield $$\left(\frac{1-\varphi}{-\varphi}\right)^{n+1} \frac{1}{-1+2\varphi} + \left(\frac{1+1/\varphi}{1/\varphi}\right)^{n+1} \frac{1}{-1-2/\varphi} \\= \frac{1}{\sqrt{5}} \frac{1}{\varphi^{2n+2}} - \frac{1}{\sqrt{5}} \varphi^{2n+2}.$$

Taking into account the sign flip this is obviously Binet / de Moivre for $${\large F_{2n+2}}.$$

Remark. If we want to do this properly we also need to verify that the residue at infinity in both cases is zero. For example in the first application we use the formula for the residue at infinity $$\mathrm{Res}_{z=\infty} h(z) = \mathrm{Res}_{z=0} \left[-\frac{1}{z^2} h\left(\frac{1}{z}\right)\right]$$

which in the present case gives for the inner term in $w$ $$- \mathrm{Res}_{w=0} \frac{1}{w^2} w^{n+1} \frac{1}{1/w-1/(1+z)} \frac{1}{1/w-(1-z)/z} \\ = - \mathrm{Res}_{w=0} w^{n+1} \frac{1}{1-w/(1+z)} \frac{1}{1-w(1-z)/z}$$ which is zero by inspection.

• I do think the variety on this page (content and contributors) is remarkable. – Marko Riedel Jul 3 '15 at 0:28