# Fibonacci induction

• Apr 25th 2013, 04:19 PM
gfbrd
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.
• Apr 25th 2013, 05:02 PM
HallsofIvy
Re: Fibonacci induction
You are going to need to use the defining property of Fibonacci series which is $f_n+ f_{n+1}= f_{n+2}$.
• Apr 25th 2013, 05:20 PM
gfbrd
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
• Apr 25th 2013, 05:53 PM
emakarov
Re: Fibonacci induction
As often happens with induction, you need to generalize the statement you are proving. Try proving

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

by induction on m.

Another method is to use matrix multiplication.
• Apr 25th 2013, 09:59 PM
gfbrd
Re: Fibonacci induction