Results 1 to 2 of 2

Math Help - Induction Proof- Fibonacci Numbers

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    7

    Unhappy Induction Proof- Fibonacci Numbers

    Hello.

    I am stuck on a homework problem.

    "Let U(subscript)n be the nth Fibonacci number. Prove by induction on n (without referring to the Binet formula) that U(subscript)m+n=U(subscript)m-1*U(subscript)n + U(subscript)m *U (subscript)n+1 for all positive integers m and n.

    So.. I figured out my Base case for n=1.
    Um+1=Um-1*U1+Um*U2, which equals Um+1=Um-1+Um, so it is true.

    For the Induction Step, I dont know where to go..

    Should I prove it P(K-1)--> P(K) or P(K)--> P(K+1).

    I've been trying both ways and I stuck on everything.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member Renji Rodrigo's Avatar
    Joined
    Sep 2009
    From
    Rio de janeiro
    Posts
    38
    F(n+p)=F(p)F(n+1)+F(p-1)F(n).

    by induction on p, for p=1

     F(n+1)=F(1)F(n+1)+F(0)F(n)=F(n+1) ok

    suposing for s<p+1, in special we have
    F(n+p)=F(p)F(n+1)+F(p-1)F(n)

    F(n+p-1)=F(p-1)F(n+1)+F(p-2)F(n)

    lets prove for p+1
    F(n+p+1)=F(p+1)F(n+1)+F(p)F(n) .

    we have
    F(n+p+1)=F(n+p)+F(n+p-1)= by the fibonacci recurrence so

    = F(p-1)F(n+1)+F(p-2)F(n) +F(p)F(n+1)+F(p-1)F(n)=


    =F(n+1)[F(p)+F(p-1)]+F(n)[F(p-2)+F(p-1)]=F(p+1)F(n+1)+F(p)F(n) .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction on Fibonacci numbers
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 27th 2010, 12:00 PM
  2. Math induction: Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 12th 2010, 04:06 PM
  3. Induction with Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 5th 2009, 10:00 AM
  4. Induction and Fibonacci Numbers
    Posted in the Algebra Forum
    Replies: 3
    Last Post: January 5th 2009, 09:42 AM
  5. Help with induction for Fibonacci Numbers
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: April 23rd 2007, 08:37 AM

Search Tags


/mathhelpforum @mathhelpforum