[Math] Prove the given property of the Fibonacci numbers directly

discrete mathematicsfibonacci-numbers

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!

Best Answer

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

Related Question