Source and/or combinatorial interpretation for $F_{n+k} = \sum_{i=0}^{k} \binom{k}{i}F_{n-i}$ 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?
 A: 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*}$$
A: 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$.
