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

• my first thought is about how the rows of pascals triangle sum to $2^n$ on row n. – user451844 Aug 21 '17 at 22:21

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

• That is pretty cool. – green frog Aug 21 '17 at 22:42

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}

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