Sum of products of Fibonacci numbers and combination values. I'm a high school teacher and students had to see the pattern I have below but they didn't have to prove it. However, an intrepid student asked me to prove it and I am stumped. I scoured the internet but I couldn't find any help. Please help me get started! The identity is below. F0=0, F1=1, F2=1, F3=2, ..., Fn=nth Fibonacci number. 
(nC0)(Fk)+(nC1)(Fk+1)+(nC2)(Fk+2)+...+(nCn)(Fk+n) = Fk+2n
 A: If $M$ is the matrix $\pmatrix{1 & 1\cr 1 & 0\cr}$, we have $M^n = \pmatrix{F_{n+1} & F_n\cr F_n & F_{n-1}}$ (well-known and easy to prove by induction).
Then using the binomial theorem and the fact that $M+I = M^2$,
$$ \sum_{j=0}^n {}_nC_j M^{k+j} =  M^k (M+I)^n = M^{k+2n}$$
and your identity follows by taking the matrix elements.
More prosaically, you can prove your identity by induction, using the fact that
${}_{n+1}C_j = {}_nC_{j-1} + {}_nC_{j}$.
A: Recall Binet's formula for Fibonacci's numbers:
$$F_n = \frac{\alpha^n - \beta^n}{\sqrt{5}}
\quad\text{ where }\quad 
\alpha = \frac{1+\sqrt{5}}{2}, \beta = \frac{1-\sqrt{5}}{2}
$$
Using Binomial theorem and notice $\alpha, \beta$ are roots of the equation $\lambda^2 = \lambda + 1$, we have
$$\begin{align}
\sum_{s=0}^n \binom{n}{s}F_{k+s}
&= \frac{1}{\sqrt{5}}\left[\alpha^k\left(\sum_{s=0}^n \binom{n}{s} \alpha^s\right) - \beta^k\left(\sum_{s=0}^n \binom{n}{s} \beta^s\right)\right]\\
&= \frac{1}{\sqrt{5}}\left[\alpha^k(\alpha+1)^n - \beta^k(\beta+1)^n\right]\\
&= \frac{1}{\sqrt{5}}\left[\alpha^{k+2n} - \beta^{k+2n}\right]\\
&= F_{k+2n}
\end{align}
$$
A: Hint : Use the two famous recursive relations $~F_{i+1}~=~F_i~+~F_{i-1}~$ and 
$C_{n+1}^{k+1}~=~C_n^k~+~C_n^{k+1}~$ in order to ultimately establish a proof by induction :

$$\begin{align}
F_m
~&=~F_{m-1}~+~F_{m-2}
~&=~C_1^0~F_{m-1}~+~C_1^1~F_{m-2}
\qquad\qquad\quad~
\\\\
~&=~\Big(F_{m-2}~+~F_{m-3}\Big)~+~\Big(F_{m-3}~+~F_{m-4}\Big)
~&=~C_2^0~F_{m-2}~+~C_2^1~F_{m-3}~+~C_2^2~F_{m-4}
\\\\
~&=~\ldots
~&=~\ldots
\qquad\qquad\qquad\qquad\qquad\qquad\quad
\end{align}$$

Can you take it from here ?...
