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.

Thanks!

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

2 Answers 2

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

$$F(n+3)=F(n+2)+F(n+1)\;.\tag{1}$$

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

$$F(n+3)=F(n+2)+F(n+1)=\Big(F(n+1)+F(n)\Big)+F(n+1)\;.$$

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
add comment

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
add comment

Your Answer

 
discard

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.