Results 1 to 3 of 3
Like Tree1Thanks
  • 1 Post By HallsofIvy

Thread: Fibonacci relative prime proof

  1. #1
    Newbie
    Joined
    Nov 2018
    From
    Montreal
    Posts
    3

    Fibonacci relative prime proof

    Hey Guys, learning discrete math by myself and while I was working with a proof, I got stuck, I checked the solution and I understand the big picture but I can't seem to understand the arithmetic, here's how it goes:

    By induction Let P(n) be the proposition that Fn and Fn+1 are relatively prime.

    Base case: P (0) is true because F0 = 0 and F1 = 1 are relatively prime.


    Inductive step: We show that, for all n 0, P(n) implies P(n + 1). So, fix some n 0and assume that P (n) is true, that is, Fn and Fn+1 are relatively prime. We will show thatFn+1 and Fn+2 are relatively prime as well. We will do this by contradiction.

    Suppose
    Fn+1 and Fn+2 are not relatively prime. Then they have a common divisor d > 1.But then d also divides the linear combination Fn+2 Fn+1, which actually equals Fn. Hence, d > 1 divides both Fn and Fn+1. Which implies Fn, Fn+1 are not relatively prime, a contradiction to the inductive hypothesis.

    Therefore,
    Fn+1 and Fn+2 are relatively prime. That is, P (n
    + 1) is true.


    How in the hell
    Fn+2 Fn+1 equals Fn ??
    Attached Thumbnails Attached Thumbnails Fibonacci relative prime proof-screen-shot-2018-11-06-7.52.31-pm.png  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    20,032
    Thanks
    3160

    Re: Fibonacci relative prime proof

    Seriously? The Fibonacci numbers are defined by $\displaystyle F_{n+2}= F_n+ F_{n+1}$. Subtract $\displaystyle F_{n+1}$ from both side.
    Thanks from kaisuketrax
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2018
    From
    Montreal
    Posts
    3

    Re: Fibonacci relative prime proof

    Yeah well I'm dumb sorry ...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: Sep 18th 2018, 04:55 AM
  2. Replies: 3
    Last Post: Apr 20th 2015, 04:34 PM
  3. Replies: 0
    Last Post: Sep 6th 2012, 01:41 AM
  4. Replies: 2
    Last Post: May 4th 2011, 03:02 PM
  5. Relatively prime and fibonacci
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Nov 23rd 2009, 07:53 AM

Search Tags


/mathhelpforum @mathhelpforum