Results 1 to 3 of 3

Math Help - prove any 2 successive terms of fibonacci sequence are relatively prime

  1. #1
    Member
    Joined
    Aug 2008
    Posts
    249

    prove any 2 successive terms of fibonacci sequence are relatively prime

    for the fibonacci sequuence, show that (x_(n+1), x_n) = 1.

    so i started by assuming that there exists at least 1 n such that x_(n+1) and x_n are not relatively prime which means that x_(n+1) = c x_n. then using the definition of the fibonacci sequence that x_(n+1) = x_n + x_(n-1), i expand the right side out until i get x_(n+1) = (n-2)c (x_2) + x_1 but x_1 = x_2 = 1 by the definition of the fibonacci sequence so i am left with x_(n+1) = (n-2)c + 1. from here i am a little stuck. before i went on to say x_n = (n-3)c + 1 and x_(n-1) = (n-4)c + 1 and used those to derive a contradiction but as i look at it now i realize that is not the correct reasoning since x_(n+1) = (n-2)c + 1 does not hold for all n. how would i be able to proceed from my last step? thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,546
    Thanks
    781
    The fact that x_(n+1) and x_n are not relatively prime does not necessarily mean that x_(n+1) = c x_n.

    See The Math Forum.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Tinyboss's Avatar
    Joined
    Jul 2008
    Posts
    433
    If a+b=c, and if d divides any two of a,b,c, then it also divides the third. So, if d divides consecutive Fibonacci numbers, then d also divides the one before that pair. Repeat the argument to show that d divides every Fibonacci number prior to that pair.
    Last edited by Tinyboss; May 4th 2011 at 02:40 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: March 1st 2010, 11:57 AM
  2. Relatively prime and fibonacci
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 23rd 2009, 06:53 AM
  3. Fibonacci Sequence
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 14th 2009, 11:47 PM
  4. Fibonacci sequence
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: September 26th 2009, 08:28 PM
  5. Fibonacci sequence - prove by induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 23rd 2008, 05:19 PM

Search Tags


/mathhelpforum @mathhelpforum