Results 1 to 7 of 7

Math Help - Induction Proof- Please Help- New to this.

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    7

    Post Induction Proof- Please Help- New to this.

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

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Laurali224 View Post
    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 am stuck on everything.
    What's the Binet formula?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2010
    Posts
    7
    Binet Formula- The Fibonacci numbers are given by the following formula:

    U(subscript)n=(alpha^n-Beta^n)/square root of 5.

    where alpha= (1+square root of 5)/2 and Beta=(1-square root of 5)/2.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Laurali224 View Post
    Binet Formula- The Fibonacci numbers are given by the following formula:

    U(subscript)n=(alpha^n-Beta^n)/square root of 5.

    where alpha= (1+square root of 5)/2 and Beta=(1-square root of 5)/2.
    Haha, that is what I was going to do. I'll let another member work through this, and if no one does by the time I come back I'll give it a go.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Feb 2010
    Posts
    7
    k thanks.


    So far I have for the Inductive Part-

    Hypothesis..

    If U(subscript) m+k-1= U(subscript)m-1*U(subscript)k-1 + U(subscript)m * U(subscript)k THEN U(sub)m+k=U(sub)m-1* U(sub)k +U(sub)m *U(sub)k+1.

    So I am working with P(k-1)--> P(k) ...

    SO I want to show [U(sub)m+k=U(sub)m-1* U(sub)k +U(sub)m *U(sub)k+1] is true.

    So I began with U(sub) m+k=U(sub)m+k+1 + U(sub) m+k-2. But I think I am already lost.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Apr 2008
    Posts
    1,092
    Let n = 1, and consider U_1 = U_2 = 1, U_3 = 2.

    Then the rule given says U_{m+1} = U_{m-1} \cdot U_1 + U_m \cdot U_2; that is

    U_{m+1} = U_{m-1} + U_m, which is true.

    Also U_{m+2} = U_{m-1} \cdot U_2 + U_m \cdot U_3;

    U_{m+2} = U_{m-1} + 2 \cdot U_m = (U_{m-1} + U_m) + U_m = U_{m+1} + U_m and the first step is complete.

    Now suppose U_{m+k} = U_{m-1} \cdot U_k + U_m \cdot U_{k+1} is true for all k \leq n.

    Then (1) U_{m+n-1} = U_{m-1} \cdot U_{n-1} + U_m \cdot U_n and

    (2) U_{m+n}= U_{m-1} \cdot U_n + U_m \cdot U_{n+1}.

    Now by the recursion, U_{m+n+1} = U_{m+n-1} + U_{m+n},

    which is, according to the formulas (1) and (2) above:

    U_{m-1} \cdot U_n + U_m \cdot U_{n+1} + U_{m-1} \cdot U_{n-1} + U_m \cdot U_n =

    U_{m-1} \cdot (U_n + U_{n-1}) + U_m \cdot (U_{n+1} + U_n) = (according to the recursion)

    U_{m-1} \cdot U_{n+1} + U_m \cdot U_{n+2},

    and the induction is complete.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Hi Laurali224,

    U_{m+k}=U_{m-1}U_k+U_mU_{k+1} ?

    If so, then the following should be true

    U_{m+k+1}=U_{m-1}U_{k+1}+U_mU_{k+2}

    Hence, we try to prove that by using the equation on the first line.

    Since U_k=U_{k+1}-U_{k-1} and U_{k+1}=U_{k+2}-U_n

    then

    U_{m+k+1}=U_{m+k}+U_{m+k-1}=U_{m-1}U_k+U_mU_{k+1}+U_{m+k-1}

    =U_{m-1}U_{k+1}-U_{m-1}U_{k-1}+U_mU_{k+2}-U_mU_k+U_{m+k-1}

    =U_{m-1}U_{k+1}+U_mU_{k+2}+\left(U_{m+k-1}-U_mU_k-U_{m-1}U_{k-1}\right)

    which is true given that we must have U_{m+k-1}=U_mU_k+U_{m-1}U_{k-1}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by induction
    Posted in the Algebra Forum
    Replies: 13
    Last Post: January 31st 2011, 04:41 PM
  2. an induction proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 5th 2009, 01:31 PM
  3. proof by induction ...
    Posted in the Calculus Forum
    Replies: 2
    Last Post: August 8th 2009, 02:07 PM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum