fibonacci-numbers
The definition of a Fibonacci number is as follows:
$$F(0)=0\\
F(1)=1\\
F(n)= F(n-2)+F(n-1)\text{ for }n\geq 2$$
Prove the given property of the Fibonacci numbers directly from the definition.
$F(n+3)=2F(n+1)+ F(n)$ for $n$ greater than or equal to $0$.
To get started:
-I would do a direct proof.
Assume that $F(0)=0$; $F(1)=1$; $F(n)= F(n-2)+F(n-1)$ for $n$ greater than or equal to $2$.
I am lost. Can I have a clue on the nest step?
This identity is clear from the following diagram:
(imagine here a generalized picture with $F_i$ notation)
The area of the rectangle is obviously
$$F_n(F_{n}+F_{n-1})=F_nF_{n+1}$$
On the other hand, since the area of a square is x^2, it is obviously:
$$F_1^2+F_2^2+\dots+F_n^2$$
Therefore:
$$F_1^2+F_2^2+\dots+F_n^2=F_nF_{n+1}$$
You can even convert this graphical proof to an inductive proof - your inductive step would consist of adding a square $F_{n+1} * F_{n+1}$.
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*}$$
Best Answer
$$ F(n+3) = \color{red}{F(n+2)} + \color{blue}{F(n+1)} = \color{red}{F(n+1)} + \color{red}{F(n)} + \color{blue}{F(n+1)} = \color{green}{2F(n+1)} + \color{red}{F(n)} $$