Source and/or combinatorial interpretation for $F_{n+k} = \sum_{i=0}^{k} \binom{k}{i}F_{n-i}$

Question

Through some fussing with Taylor's Theorem in the discrete calculus described here (among other places), I found what I believe to be an identity:

$$F_{n+k} = \sum_{i=0}^{k} \binom{k}{i}F_{n-i}$$

For example, with $n = 3$ and $k = 3$: $$ \begin{aligned} F_6 &= 8\\ &= \binom{3}{0}F_3 + \binom{3}{1}F_2 + \binom{3}{2}F_1 + \binom{3}{3}F_0\\ &= F_3 + 3F_2 + 3F_1 + F_0\\ &= 2 + 3(1) + 3(1) + 0\\ \end{aligned} $$

and with $n = 4$ and $k = 2$:

$$ \begin{aligned} F_6 &= 8\\ &= \binom{2}{0}F_4 + \binom{2}{1}F_3 + \binom{2}{2}F_2\\ &= F_4 + 2F_3 + F_2\\ &= 3 + 2(2) + 1\\ \end{aligned} $$

I'd like to find a source/alternate proof, but I don't know how to search for this kind of thing, beyond googling "Fibonacci binomial identity" which hasn't so far been successful.

I know there are an insane number of Fibonacci identities out there; is this a special case of something else?

Also, is there a nice combinatorial interpretation?

Answer 1

The explicit formula for Fibonacci numbers gives: $$ F_n = \frac{1}{\sqrt{5}}\left(\sigma^n-\overline{\sigma}^n\right) $$ where $\sigma,\overline{\sigma}$ are solutions of $x^2=1+x$. By the binomial theorem it follows that:

$$ \sum_{i=0}^{k}\binom{k}{i}F_{n-i} = F_{n+k}. \tag{1}$$ On the other hand, the LHS of $(1)$ is the coefficient of $x^n$ in the product between $(1+x)^k$ and the generating function of Fibonacci numbers: $$\begin{eqnarray*} \sum_{i=0}^{k}\binom{k}{i}F_{n-i} = [x^n]\frac{x(1+x)^k}{1-x-x^2}&=&[x^{n+k}]\frac{x(x+x^2)^k}{1-x-x^2}\\&=&[x^{n+k}]\frac{x\left(1-(1-x-x^2)\right)^k}{1-x-x^2}\\&=&[x^{n+k}]\frac{x}{1-x-x^2}=F_{n+k}.\tag{2}\end{eqnarray*}$$

Answer 2

Here is a proof that does not use generating functions but rather elementary methods, that is, mathematical induction over $k$.

For $k=0$, it's just $F_n=F_n$ which is quite true..

For $k=1$, it's $F_{n+1}=F_n+F_{n-1}$ which is true by the definition of the Fibonacci Numbers.

Let's proceed to the induction step. Assume we proved it for some $k$ and for $k-1$. Then, using the well-known $\binom{a}{b}=\binom{a-1}{b}+\binom{a-1}{b-1}$ and $\binom{k}{-1}=\binom{k}{k+1}=0$ we have $$\sum_{i=0}^{k+1} \binom{k+1}{i} F_{n-i}=\sum_{i=0}^{k+1} \left(\binom{k}{i}+\binom{k}{i-1} \right) F_{n-i}=\sum_{i=0}^{k+1} \binom{k}{i} F_{n-i}+\sum_{i=0}^{k+1} \binom{k}{i-1} F_{n-i}=\sum_{i=0}^{k} \binom{k}{i} F_{n-i}+\sum_{i=0}^{k} \binom{k}{i} F_{n-1-i}$$ But now we can evoke the induction hypothesis and hence obtain $$\sum_{i=0}^{k+1} \binom{k+1}{i} F_{n-i}=F_{n+k}+F_{n+k-1}=F_{n+k+1}$$

Thus, we proved the induction step and hence established the result for all possible $n,k$.