Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The definition of the Fibonacci numbers is as follows: $F(0)=0$, $F(1)=1$, $F(n)=F(n-2)+F(n-1)$ for $n ≥ 2$.

  1. Prove the given property of the Fibonacci numbers directly from the definition (hint: do a direct proof): (1 point) $$F(n + 3) = 2F(n + 1) + F(n) \text{ for } n ≥0$$

I'm trying to really understand the steps of the proof, not just get the answer. Please explain each step. I've already seen the solution but I'm confused.


share|improve this question
Who will get the (1 point) for the answer? –  Marc van Leeuwen Sep 28 '13 at 3:40

2 Answers 2

First use the definition to expand $F(n+3)$. Each Fibonacci number is the sum of the two previous ones, so


Now expand $F(n+2)$ the same way: $F(n+2)=F(n+1)+F(n)$, so $(1)$ becomes


And now all that’s left is to collect terms:

$$\begin{align*} F(n+3)&=F(n+2)+F(n+1)\\ &=\Big(F(n+1)+F(n)\Big)+F(n+1)\\ &=2F(n+1)+F(n)\;. \end{align*}$$

share|improve this answer

This is just a calculation, no arguments are used. Write down $F(n+3)$, apply the recursion relation to express it in terms of $F(n+2)$ and $F(n+1)$, then apply the relation to $F(n+2)$ in turn so that it disappears from the expression (but $F(n)$ appears). After combining terms one gets the result.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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