
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.

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

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

Re: Fibonacci induction
As often happens with induction, you need to generalize the statement you are proving. Try proving
$\displaystyle u_{n+m} = u_{n1}u_m + u_n u_{m+1}$
by induction on m.
Another method is to use matrix multiplication.

Re: Fibonacci induction
Thanks for your help emakarov