Results 1 to 8 of 8

Math Help - Fibonacci Induction Proofs

  1. #1
    Junior Member
    Joined
    Jul 2009
    Posts
    25

    Fibonacci Induction Proofs

    I have 2 proofs relating to Fibonacci numbers and each other.

    1. F_m+n = (F_m-1)(F_n) + (F_m)(F_n+1) for m≥1 and n≥0. (_ indicates subscript)

    So far I have,
    I am letting m be fixed and using induction on n.
    Basis: n = 0, LHS: F_(m+0) = F_m
    RHS: F_(m-1)*F_(0) + F_(m)*F_(0+1) = F_m

    Induction Hypothesis: n = k, F_(m+k) = F_(m-1)*F_k + F_m*F_(k+1)
    Induction Step: n=k+1, F_[m+(k+1)] = F_(m-1)*F_(k+1) + F_m*F_[(k+1)+1]
    I am not sure where to go from here, can anyone help?

    Then 2. Prove that for all m≥1 and n≥1, F_m divides F_(m*n). I am to do induction on n and use what I found in part 1 to help.

    Thanks
    Last edited by CaptainBlack; October 16th 2009 at 08:17 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Oct 2009
    Posts
    95
    Quote Originally Posted by CoraGB View Post
    I have 2 proofs relating to Fibonacci numbers and each other.

    1. F_m+n = (F_m-1)(F_n) + (F_m)(F_n+1) for m≥1 and n≥0. (_ indicates subscript)

    So far I have,
    I am letting m be fixed and using induction on n.
    Basis: n = 0, LHS: F_(m+0) = F_m
    RHS: F_(m-1)*F_(0) + F_(m)*F_(0+1) = F_m

    Induction Hypothesis: n = k, F_(m+k) = F_(m-1)*F_k + F_m*F_(k+1)
    Induction Step: n=k+1, F_[m+(k+1)] = F_(m-1)*F_(k+1) + F_m*F_[(k+1)+1]
    I am not sure where to go from here, can anyone help?

    Then 2. Prove that for all m≥1 and n≥1, F_m divides F_(m*n). I am to do induction on n and use what I found in part 1 to help.

    Thanks

    Hi there,

    For the first part you need to use "strong" induction, that is you need more than one previous case to prove the next (you need 2.)

    So for part one:

    The base case:

    F_{m+1} = F_{m-1} + F_{m} = F_{m-1} F_1 + F_{m} F_2

    and

    F_{m+2} = F_{m} + F_{m+1} = F_{m} + F_{m-1} + F_{m} = 2 F_m + F_{m-1} = F_{m-1}  F_2 + F_{m} F_3

    Then

    <br />
F_{m+n} = F_{m+n-1} + F_{m+n-2} = (F_{m-1} F_{n-1} + F_m F_n) + (F_{m-1}F_{n-2} + F_m F_{n-1})<br />

    using the induction hypothesis on the case n-1 and n-2.

    Then
    <br />
(F_{m-1} F_{n-1} + F_m  F_n) + (F_{m-1}F_{n-2} + F_m F_{n-1})<br />

    <br />
 = F_{m-1}(F_{n-1} + F_{n-2}) + F_m (F_n + F_{n-1}) = F_{m-1} F_n + F_m F_{n+1}<br />


    For the second part


    Clearly,  F_m | F_m for the base case.


    Then

     F_{nm} = F_{m + (n-1)m} = F_{m-1} F_{(n-1)m} + F_m F_{(n-1)m +1}

    where F_m | F_{(n-1)m} by the induction hypothesis proving the result.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jul 2009
    Posts
    25
    Thanks so much!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie opsahl92's Avatar
    Joined
    Aug 2009
    From
    Norway : )
    Posts
    7
    Sorry for bumping this old topic, but I am trying to understand the first proof, and can't get my head around the 2nd last step:

    (F_{m-1} F_{n-1} + F_m  F_n) + (F_{m-1}F_{n-2} + F_m F_{n-1})=F_{m-1}(F_{n-1} + F_{n-2}) + F_m (F_n + F_{n-1})

    More presicely what I don't understand is:
    \frac{F_m  F_n}{F_{m-1}}=F_{n-2}

    and

    \frac{F_{m-1}F_{n-2}}{F_{m}}=F_n

    (At least I think that is what is happening)

    Would anyone care to explain to me why this is allowed?
    Last edited by opsahl92; May 4th 2010 at 09:04 AM. Reason: Messed up LaTeX
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2009
    Posts
    95
    Quote Originally Posted by opsahl92 View Post
    Sorry for bumping this old topic, but I am trying to understand the first proof, and can't get my head around the 2nd last step:

    (F_{m-1} F_{n-1} + F_m  F_n) + (F_{m-1}F_{n-2} + F_m F_{n-1})=F_{m-1}(F_{n-1} + F_{n-2}) + F_m (F_n + F_{n-1})

    More presicely what I don't understand is:
    \frac{F_m  F_n}{F_{m-1}}=F_{n-2}

    and

    \frac{F_{m-1}F_{n-2}}{F_{m}}=F_n

    (At least I think that is what is happening)

    Would anyone care to explain to me why this is allowed?
    I'm sorry I'm not following the question. You will have to explain what you mean with more detail. I don't know where you got

    \frac{F_m  F_n}{F_{m-1}}=F_{n-2}

    from (thats actually not used in the proof, in fact its probably false.) Try explaining your reasoning.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie opsahl92's Avatar
    Joined
    Aug 2009
    From
    Norway : )
    Posts
    7
    Quote Originally Posted by gmatt View Post
    ...

    Then
    <br />
(F_{m-1} F_{n-1} + F_m  F_n) + (F_{m-1}F_{n-2} + F_m F_{n-1})<br />

    <br />
 = F_{m-1}(F_{n-1} + F_{n-2}) + F_m (F_n + F_{n-1})

    (Direct quote from your post! )

    I just can't figure out how you got from the first to the 2nd line!

    I got the fractions by pulling F_{m-1} and F_m out of the parenthesises in the first line of the quote.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Oct 2009
    Posts
    95
    Quote Originally Posted by opsahl92 View Post
    (Direct quote from your post! )

    I just can't figure out how you got from the first to the 2nd line!

    I got the fractions by pulling F_{m-1} and F_m out of the parenthesises in the first line of the quote.
    Ahh! I see what you mean now. Yes sorry, I should of made that step more explicit, its just a rearrangement of terms:

    <br />
 (F_{m-1} F_{n-1} + F_m  F_n) + (F_{m-1}F_{n-2} + F_m F_{n-1})<br />
    <br />
=<br />
(F_{m-1} F_{n-1} + F_{m-1}F_{n-2}) + (F_m F_n + F_m F_{n-1})<br />
    <br />
=<br />
F_{m-1}(F_{n-1} + F_{n-2}) + F_m (F_n + F_{n-1})<br />
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie opsahl92's Avatar
    Joined
    Aug 2009
    From
    Norway : )
    Posts
    7
    I get it now!! Thank you so much! I should've noticed, though! xD
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Induction w/ Fibonacci
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 7th 2010, 08:07 PM
  2. fibonacci sequence proofs
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: September 30th 2009, 11:12 AM
  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