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! :)

Solution 1:

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.

Solution 2:

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}

Solution 3:

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

Solution 4:

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

Solution 5:

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

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}