1. ## Fibonacci induction

Hello I need some help with this problem

For each natural number n, let fn be the nth Fibonacci number. Prove that (f_(n+1))^2 + (f_n)^2 = f_(2n+1).

so far what I have
let n=1 so 1^2 + 1^2 = 2 which is true so the equation holds for n= 1 (base case)

then I pick an arbitrary k where (f_(k+1))^2 + (f_k)^2 = f_(2k+1)
and now I prove for k+1 so I'm trying to show

(f_(k+2))^2 + (f_(k+1)^2 = f_(2k+3)

Ive spent hours trying to manipulate this problem to show this is true but no luck so far so I am hoping someone can guide me through this problem so I know how to do it thanks.

2. ## Re: Fibonacci induction

You are going to need to use the defining property of Fibonacci series which is $\displaystyle f_n+ f_{n+1}= f_{n+2}$.

3. ## Re: Fibonacci induction

so i substituted and got (f_k + f_(k+1))^2 + (f_(k+1)^2 = f_(2k+3)
what do i do next? do I multiply it out and combine? Substitute in again for some other values?

Note: I have tried many possibilities for this problem, and substituting was one of them, it wasn't as easy as it looks

4. ## Re: Fibonacci induction

As often happens with induction, you need to generalize the statement you are proving. Try proving

$\displaystyle u_{n+m} = u_{n-1}u_m + u_n u_{m+1}$

by induction on m.

Another method is to use matrix multiplication.