Proof: $\sum^n_{i = 0} {n\choose i} F_{i+m}$ is Fibonacci number I'm trying to solve the following problem:
Show
$$\sum^n_{i = 0} {n\choose i} F_{i+m}$$
is Fibonacci number.
I know many properties of binomial symbol and Fibonacci numbers but I have no idea how to start proving given formula.
 A: Ok, I've proved it by induction. To make the proof work, one needs to use identity
$${n+1 \choose i} = {n \choose i - 1} + {n \choose i}$$
and the definition of binomial coefficients which says
$${n \choose n + i} = {n \choose -i} = 0 \text{ where } i \in \mathbb{N}^+$$
The rest of the proof is just classical, easy and beautiful induction :)
A: The task is to express
$$S_{n,m} = \sum_{q=0}^n {n\choose q} F_{q+m}$$
as a Fibonacci number. Using  the generating function of the Fibonacci
numbers we find that
$$F_{q+m} =
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{q+m+1}} \frac{z}{1-z-z^2} \; dz.$$
We thus obtain for the sum
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{m+1}} 
\frac{z}{1-z-z^2} 
\sum_{q=0}^n {n\choose q} \frac{1}{z^q}
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{m}} 
\frac{1}{1-z-z^2} 
\left(1+\frac{1}{z}\right)^n
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+m}} 
\frac{1}{1-z-z^2} (1+z)^n
\; dz.$$
Using the golden ratio $$\varphi = \frac{1+\sqrt{5}}{2}$$ this becomes
$$-\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+m}} 
\frac{1}{(z-1/\varphi)(z+\varphi)} (1+z)^n
\; dz.$$
Residues sum to zero so from the two simple poles we get
$$S_{n,m} - \frac{1}{1/\varphi+\varphi} 
\varphi^{n+m} \left(1+\frac{1}{\varphi}\right)^n
- \frac{1}{-\varphi-1/\varphi} 
\frac{1}{(-\varphi)^{n+m}} \left(1-\varphi\right)^n = 0.$$
Hence
$$S_{n,m} = \frac{1}{\varphi + 1/\varphi}
\left( \varphi^m (1+\varphi)^n
- \left(-\frac{1}{\varphi}\right)^m
\left(-\frac{1}{\varphi}+1\right)^n \right).$$
By definition we have $1+\varphi = \varphi^2$ and
$1+(-1/\varphi) = (-1/\varphi)^2$ so this becomes
$$S_{n,m} = \frac{1}{\varphi + 1/\varphi}
\left( \varphi^{m+2n}
- \left(-\frac{1}{\varphi}\right)^{m+2n}\right).$$
This is Binet's formula evaluated at $m+2n$ and we get the result
$$\bbox[5px,border:2px solid #00A000]{ F_{m+2n}.}$$
Remark. We have used the fact that
$$\mathrm{Res}_{z=\infty} \frac{1}{z^{n+m}} 
\frac{1}{1-z-z^2} (1+z)^n
\\ = -\mathrm{Res}_{z=0} \frac{1}{z^2} z^{n+m}
\frac{1}{1-1/z-1/z^2} \left(1+\frac{1}{z}\right)^n
\\ = -\mathrm{Res}_{z=0} z^{m}
\frac{1}{z^2-z-1} (1+z)^n = 0.$$
