# Fibonacci Sequence property

• Mar 2nd 2008, 10:04 AM
MatsSundin
Fibonacci Sequence property
Using normal properties of Fibonacci Numbers Prove that:
(F(n+1)^2)+(F(n)^2)= F(2n+1).
We see that F(3)=2 and F(4)=3 and so F(7)=13 so it is true
Not sure where to start here and any help would be appreciated.
• Mar 2nd 2008, 10:36 AM
Jhevon
Quote:

Originally Posted by MatsSundin
Using normal properties of Fibonacci Numbers Prove that:
(F(n+1)^2)+(F(n)^2)= F(2n+1).
We see that F(3)=2 and F(4)=3 and so F(7)=13 so it is true
Not sure where to start here and any help would be appreciated.

i suppose you are doing induction.

so, you must now assume P(n) is true and try to show that P(n + 1) must be true.

of course, here, $\displaystyle P(n)$ is "$\displaystyle F_{n + 1}^2 + F_n^2 = F_{2n + 1}$ for all integers $\displaystyle n \ge 3$"
• Mar 2nd 2008, 10:58 AM
galactus
I proved this identity back in school using Binet's formula(without induction) and some identities.

Do you have to use induction?. That is a good way to go, but I like this method I stumbled onto a while back while studying Fibonacci's for a class called Seminars in Mathematics. I doubt if it's original, but it works.

I will use $\displaystyle x=\frac{1+\sqrt{5}}{2}, \;\ y=\frac{1-\sqrt{5}}{2}$

Take note that $\displaystyle xy=-1$ and $\displaystyle x^{2}-\sqrt{5}x+1=0$ and $\displaystyle y^{2}+\sqrt{5}y+1=0$

We will use these later.

From Binet's formula: $\displaystyle \frac{x^{n}-y^{n}}{\sqrt{5}}$

We can sub it in our formula to prove:

$\displaystyle \frac{1}{5}\left[(x^{n}-y^{n})^{2}+(x^{n+1}-y^{n+1})^{2}-\sqrt{5}(x^{2n+1}-y^{2n+1})\right]$

Expand:

$\displaystyle \frac{1}{5}\left[x^{2n}-2x^{n}y^{n}+y^{2n}+x^{2n+2}-2x^{n+1}y^{n+1}+y^{2n+2}-\sqrt{5}x^{2n+1}+\sqrt{5}y^{2n+1}\right]$

Group and factor:

$\displaystyle \frac{1}{5}\left[x^{2n}(\underbrace{x^{2}-\sqrt{5}x+1}_{\text{equals 0}})+y^{2n}(\underbrace{y^{2}+\sqrt{5}y+1}_{\text{ equals 0}})-2(\underbrace{xy}_{\text{-1}})^{n}(1+xy)\right]$

Take note that everything inside the brackets is 0, due to the identities previously mentioned.

We get:

$\displaystyle \frac{1}{5}\left[x^{2n}(0)+y^{2n}(0)-2(-1)(0)\right]=0$

$\displaystyle \therefore$, $\displaystyle f^{2}_{n}+f^{2}_{n+1}=f_{2n+1}$

You can show various identities using these tools. They can be handy to know.
• Mar 2nd 2008, 04:29 PM
MatsSundin
No induction is not needed, it can be proven any way possible. Your solution is quite intuitive and impressive thank you!