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

  • $\begingroup$ my first thought is about how the rows of pascals triangle sum to $2^n$ on row n. $\endgroup$ – 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}$.

  • $\begingroup$ That is pretty cool. $\endgroup$ – 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 ?...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.