1. ## Fibonacci Number Proof

Prove that

$\displaystyle f_{2n+1} = f_{n+1}^2 + f_n^2$

for all positive integers.

I assume the solution involves induction, but I'm having trouble with this... Any pointers would be greatly appreciated. Thanks

2. Originally Posted by VinceW
Prove that

$\displaystyle f_{2n+1} = f_{n+1}^2 + f_n^2$

for all positive integers.

I assume the solution involves induction, but I'm having trouble with this... Any pointers would be greatly appreciated. Thanks
Yes, this involves induction.
For n = 1, we have "2 = 1 + 1".
For n >= 1, let's identify what we are trying to prove... i.e.

$\displaystyle f_{2(n+1) + 1} = f_{(n+1) + 1}^2 + f_{(n+1)}^2$

Now use the definition of the Fibonacci sequence, and see what comes up (should/might involve some distribution)...

3. Originally Posted by VinceW
Prove that

$\displaystyle f_{2n+1} = f_{n+1}^2 + f_n^2$

for all positive integers.

I assume the solution involves induction, but I'm having trouble with this... Any pointers would be greatly appreciated. Thanks

I suppose induction can be used here, but if you know the relation $\displaystyle \displaystyle{f_n=\frac{\phi^n-\xi^n}{\sqrt{5}}\,,\,\,\phi:=\frac{1+\sqrt{5}}{2} \, ,\,\xi:=\frac{1-\sqrt{5}}{2}}$ , then the solution

is straighforward, though you need to play algebraically quite a while with the resulting expressions.

Tonio

4. Proof, without induction (?)
Define
$\displaystyle F= \left(\begin{array}{cc}1 & 1 \\ 1 & 0 \\\end{array}\right)$

so
$\displaystyle F^n=\left(\begin{array}{cc}F(n+1) & F(n) \\F(n) & F(n-1) \\ \end{array}\right).$
(by induction)

General case
$\displaystyle F(n+p)=F(p)F(n+1)+F(p-1)F(n).$

Proof
we have the matrix identity $\displaystyle F^n F^p =F^{n+p}$
so
$\displaystyle \left(\begin{array}{cc} F(n+1) & F(n) \\F(n) & F(n-1) \\\end{array}\right)\left(\begin{array}{cc}F(p+1) & F(p) \\F(p) & F(p-1) \\\end{array}\right)= \left(\begin{array}{cc}F(n+p+1) & F(n+p) \\F(n+p) &F(n+p-1) \\\end{array}\right)$

by multiplication of the matrices
$\displaystyle F(n+p)=F(n+1)F(p)+F(n)F(p-1).$

take $\displaystyle p =n+1$

so

$\displaystyle F(2n+1)=F(n+1)^2+F(n)^2.$