# Prove the given property of the Fibonacci numbers directly

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!

-
Who will get the (1 point) for the answer? –  Marc van Leeuwen Sep 28 '13 at 3:40

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*}

-

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.

-