Proof: $\sum^n_{i = 0} {n\choose i} F_{i+m}$ is Fibonacci number

Question

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.

Answer 1

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

Answer 2

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