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! :)
 A: 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}
A: 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}.
$$
A: 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}
$$
A: $\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}
A: 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.
A: 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.
