Results 1 to 5 of 5
Like Tree1Thanks
  • 1 Post By emakarov

Math Help - Fibonacci induction

  1. #1
    Member
    Joined
    Oct 2012
    From
    san francisco
    Posts
    92

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,693
    Thanks
    1466

    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}.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2012
    From
    san francisco
    Posts
    92

    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    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.
    Thanks from gfbrd
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2012
    From
    san francisco
    Posts
    92

    Re: Fibonacci induction

    Thanks for your help emakarov
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fibonacci Induction Proofs
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: May 4th 2010, 09:39 AM
  2. Induction with Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 5th 2009, 09:00 AM
  3. Induction and Fibonacci Numbers
    Posted in the Algebra Forum
    Replies: 3
    Last Post: January 5th 2009, 08:42 AM
  4. Fibonacci, proof with induction
    Posted in the Algebra Forum
    Replies: 2
    Last Post: August 27th 2008, 10:19 AM
  5. Help with induction for Fibonacci Numbers
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: April 23rd 2007, 07:37 AM

Search Tags


/mathhelpforum @mathhelpforum