Results 1 to 7 of 7

Math Help - Fibonacci Proof

  1. #1
    Super Member redsoxfan325's Avatar
    Joined
    Feb 2009
    From
    Swampscott, MA
    Posts
    943

    Fibonacci Proof

    I hate to say this, but...I'm stuck on an induction proof. I'm trying to prove that \gcd(F_m,F_n)=F_{\gcd(m,n)}, where F_j is the jth Fibonacci number. I have it reduced to proving that F_m\,|\,F_{qm} for all m. I have the rest of the proof.

    So I tried proving it with induction.

    It's trivial for m=1, so I assumed F_m\,|\,F_{qm}. Then I tried to prove that F_{m+1}\,|\,F_{qm+q}.

    Using an identity I know and have proved,

    F_{qm+q}=F_qF_{qm+1}+F_{q-1}F_{qm}=F_qF_{qm+1}+kF_{q-1}F_m

    for some k\in\mathbb{N}, but now I'm stuck.

    Any hints?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by redsoxfan325 View Post
    I hate to say this, but...I'm stuck on an induction proof. I'm trying to prove that \gcd(F_m,F_n)=F_{\gcd(m,n)}, where F_j is the jth Fibonacci number. I have it reduced to proving that F_m\,|\,F_{qm} for all m. I have the rest of the proof.

    So I tried proving it with induction.

    It's trivial for m=1, so I assumed F_m\,|\,F_{qm}. Then I tried to prove that F_{m+1}\,|\,F_{qm+q}.

    Using an identity I know and have proved,

    F_{qm+q}=F_qF_{qm+1}+F_{q-1}F_{qm}=F_qF_{qm+1}+kF_{q-1}F_m

    for some k\in\mathbb{N}, but now I'm stuck.

    Any hints?
    Hint: Do induction on 'q' rather than m. That should do it.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member redsoxfan325's Avatar
    Joined
    Feb 2009
    From
    Swampscott, MA
    Posts
    943
    I can do that, but does that prove the same thing as induction on m? (Because the idea was supposed to be that q is constant and m is the variable.)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by redsoxfan325 View Post
    I can do that, but does that prove the same thing as induction on m? (Because the idea was supposed to be that q is constant and m is the variable.)
    I guess you want to prove that the above is true for any +ve integers m,q

    So you can induct on m and under the induction hypothesis prove it is true for all q.

    Or you can induct on q and under the induction hypothesis prove it is true for all m.

    If you think carefully both prove the original statement. Atleast I'm pretty convinced.

    The reason to chose 2nd approach is that the result is closely tied to induction on q rather than induction on m. It's almost trivial that way.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by aman_cc View Post
    I guess you want to prove that the above is true for any +ve integers m,q

    So you can induct on m and under the induction hypothesis prove it is true for all q.

    Or you can induct on q and under the induction hypothesis prove it is true for all m.

    If you think carefully both prove the original statement. Atleast I'm pretty convinced.

    The reason to chose 2nd approach is that the result is closely tied to induction on q rather than induction on m. It's almost trivial that way.

    You may want to look at a similar post I did a few days ago -
    http://www.mathhelpforum.com/math-he...tml#post410668

    Your original problem follows directly from the identity, I wrote there. This is just FYI
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member redsoxfan325's Avatar
    Joined
    Feb 2009
    From
    Swampscott, MA
    Posts
    943
    Yes, I agree that the second method is quite easy. I'll think about this until I'm convinced that inducting on q gives the same result.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by redsoxfan325 View Post
    Yes, I agree that the second method is quite easy. I'll think about this until I'm convinced that inducting on q gives the same result.
    Sure. I can help you prove that if you are not convinced. Please note the 'for all' in my post above. That would be critical in the proof I will give (for induction on 'q')
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fibonacci Proof II
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 16th 2011, 03:04 AM
  2. Fibonacci Proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 5th 2011, 02:47 AM
  3. Fibonacci Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 5th 2009, 08:08 AM
  4. Another Fibonacci Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 11th 2008, 04:17 AM
  5. another fibonacci proof
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 16th 2007, 07:10 AM

Search Tags


/mathhelpforum @mathhelpforum