Prove a formula with Fibonacci sum

Question

Prove that $$\binom{n}{1}F_1 + \binom{n}{2}F_2 + \dots + \binom{n}{n - 1}F_{n-1} + F_n = F_{2n},$$ where $F_n$ denotes the $n$-th Fibonacci number.

I have already tried using induction. Base case $n=1$ is easy, but once I assume $n=k$ is true, I do not know how to use this to prove the case when $n=k+1$.

Thanks a lot.

Answer 1

You may use induction by recalling the recursive formulas for the binomial coefficients and the Fibonacci numbers. For a direct proof use the Binet's formula $$F_n=\frac{\varphi^n-(-1/\varphi)^{n}}{\sqrt{5}}$$ where $\varphi=\frac{1+\sqrt{5}}{2}$ and $-1/\varphi$ are the solutions of the equation $x^2=x+1$, and the binomial theorem $$\sum_{k=0}^n\binom{n}{k}a^k=(1+a)^n.$$ Can you take it from here?

Answer 2

Sometimes you can do a fairly straightforward induction proof if you prove more than what's asked for. In this case, let's prove, by induction, two identities:

$${n\choose1}F_1+{n\choose2}F_2+\cdots+{n\choose n}F_n=F_{2n}$$ and $${n\choose0}F_1+{n\choose1}F_2+\cdots+{n\choose n}F_{n+1}=F_{2n+1}$$

The base cases are easy: ${1\choose1}F_1=F_1=1=F_2$ and ${1\choose0}F_1+{1\choose1}F_2=F_1+F_2=1+1=2=F_3$.

For the inductive step, recall that

$${n+1\choose k}={n\choose k}+{n\choose k-1}$$

Thus, with apologies for the ungainliness of the formulas,

$${n+1\choose1}F_1+{n+1\choose2}F_2+\cdots+{n+1\choose n}F_n+{n+1\choose n+1}F_{n+1} =\left({n\choose1}F_1+{n\choose2}F_2+\cdots+{n\choose n}F_n \right)+\left({n\choose0}F_1+{n\choose1}F_2+\cdots+{n\choose n}F_{n+1} \right)\\ =F_{2n}+F_{2n+1}\\=F_{2n+2}$$

and (remembering that $F_0=0$)

$${n+1\choose0}F_1+{n+1\choose1}F_2+\cdots+{n+1\choose n}F_{n+1}+{n+1\choose n+1}F_{n+2} =\left({n\choose0}F_1+{n\choose1}F_2+\cdots+{n\choose n}F_{n+1} \right)+\left({n\choose0}F_2+{n\choose1}F_3+\cdots+{n\choose n}F_{n+2} \right) =\left({n\choose0}F_1+{n\choose1}F_2+\cdots+{n\choose n}F_{n+1} \right)+\left({n\choose0}(F_1+F_0)+{n\choose1}(F_2+F_1)+\cdots+{n\choose n}(F_{n+1}+F_n) \right) =2\left({n\choose0}F_1+{n\choose1}F_2+\cdots+{n\choose n}F_{n+1} \right)+\left({n\choose1}F_1+{n\choose2}F_2+\cdots+{n\choose n}F_n \right)\\ =2F_{2n+1}+F_{2n}\\=F_{2n+1}+(F_{2n+1}+F_{2n})\\=F_{2n+1}+F_{2n+2}\\=F_{2n+3}$$

Remark: I did not know the second identity in advance. Basically I just started writing out the inductive step for the first identity, as shown, and saw there was a second identity that needed to be proved.