3
$\begingroup$

$$ F_{2n} = F_n (F_{n+1} + F_{n-1}) $$

I'm so stuck. I've used the definition of Fibonacci to change $F_{2n+2}$ into $F_{2n+1} + F_{2n}$. Can't use other properties, only the inductive hypothesis and the definition of Fibonacci.

$\endgroup$
3
  • 1
    $\begingroup$ If you know (or you are able to prove) that $F_{2n}=F_n L_n$, where $L_n$ is a Lucas number, the problem boils down to showing that $L_n=F_{n-1}+F_{n+1}$, trivial by induction. $\endgroup$ Oct 30, 2015 at 16:43
  • $\begingroup$ @Jean-ClaudeArbaut sorry it was an accident I was editing on my phone $\endgroup$ Oct 30, 2015 at 16:59
  • $\begingroup$ @JackD'Aurizio we haven't started using the Lucas number $\endgroup$ Oct 30, 2015 at 16:59

3 Answers 3

7
$\begingroup$

Here is a solution which includes only basic combinatorial arguments:

A famous combinatorial interpretation of the Fibonacci Numbers (which is also easy to prove inductively) is the following:

$F_n$ is the number of possibilities to walk up $n-1$ stairs where every step is either one, either two stairs.

Now, we count the number of possible walks on $(2n-1)$ stairs in two different manners.

On the one side, this is (by the above interpretation) equal to $F_{2n}$.

On the other side, we can distinguish two cases:

If such a walk contains a step onto the $n$-th stair, there are clearly $F_nF_{n+1}$ possibilities.

If it does not contain that step, it must contain the $(n-1)$-th and the $(n+1)$t-h stair, i.e. there are $F_{n-1} \cdot F_n$ possibilities.

Thus, the total number of possible walks is $$F_{2n}=F_n(F_{n-1}+F_{n+1})$$ which is exactly the desired identity.

$\endgroup$
0
5
$\begingroup$

This follows from the matrix formulation, which is well worth knowing and easily proved: $$ \begin{pmatrix}1&1\\1&0\end{pmatrix}^n= \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix} $$ Just compare $$ \begin{pmatrix}1&1\\1&0\end{pmatrix}^{2n}= \begin{pmatrix}*&F_{2n}\\*&*\end{pmatrix} $$ with $$ \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}^2= \begin{pmatrix}*&\cdots\\*&*\end{pmatrix} $$

$\endgroup$
2
  • $\begingroup$ We're not using matrices to solve but thank you $\endgroup$ Oct 30, 2015 at 16:58
  • $\begingroup$ @lhf This is one of those things which is so painfully obvious in retrospect $\endgroup$ Oct 30, 2015 at 16:58
1
$\begingroup$

(Late but after a duplicate was asked)

If you also assert something like $F_{2n-1} = F_n^2+F_{n-1}^2$ as well, then you can prove the two together by induction over $n$, showing:

  • $F_{2k+1}=F_{2k-1}+F_{2k} =F_k^2+F_{k-1}^2 +F_kF_{k-1}+F_kF_{k+1} = F_k^2+F_{k+1}^2$
  • $F_{2k+2}=F_{2k}+F_{2k+1} =F_kF_{k+1} +F_kF_{k-1}+F_k^2+F_{k+1}^2= F_kF_{k+1}+F_{k+2}F_{k+1}$

as well as checking the early terms

$\endgroup$

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.