Prove a formula with Fibonacci sum 
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. 
 A: 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?
A: 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.
