<s>[INST] 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! :)
 [/INST] 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}
</s>