Results 1 to 2 of 2

Math Help - Help with proof regarding fibonacci sequence

  1. #1
    Newbie
    Joined
    May 2008
    Posts
    11

    Help with proof regarding fibonacci sequence

    The Fibonacci sequence is given:
    A1 = A2 = 1 , An = An-1 + An-2

    For m >= 1 and n >= 1 Prove that Amn is divisible by Am.

    I have already prepared and proved by induction a Lemma which is:
    For m >= 2 and n > = 1. Fibonacci sequence satisfies:
    Am+n = Am-1An + AmAn+1

    The consequence of the Lemma allows me to rewrite Amn as:
    Am(k+1)= Amk+m = Amk-1Am + AmkAm+1.

    So now, I believe I'm suppose to convert that equation to
    Amk+m = Am(Some integer).

    Been going at it for hours, I'm starting to think I'm approaching it wrong. Thanks in advance!!!
    Last edited by erockdontstop; March 14th 2013 at 10:42 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: Help with proof regarding fibonacci sequence

    You can prove that Amk is divisible by Am by induction on k. Then the first term of Amk-1Am + AmkAm+1 is clearly divisible by Am and the second term is divisible by the induction hypothesis.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fibonacci sequence divisibility proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: June 20th 2011, 04:46 AM
  2. Fibonacci sequence proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 5th 2011, 02:29 AM
  3. Fibonacci sequence proof
    Posted in the Algebra Forum
    Replies: 3
    Last Post: May 20th 2010, 07:28 AM
  4. Fibonacci Sequence Proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 15th 2009, 07:40 PM
  5. Fibonacci sequence proof
    Posted in the Algebra Forum
    Replies: 3
    Last Post: April 30th 2007, 09:12 AM

Search Tags


/mathhelpforum @mathhelpforum