Results 1 to 3 of 3

Math Help - Fibonacci Numbers - proof.

  1. #1
    Member
    Joined
    Sep 2007
    Posts
    127

    Fibonacci Numbers - proof.

    Afternoon guys I'm considering 2 ways of approaching this question. One is significantly easier than the other, but I wanted to know if it is a valid method - or rigorous and formal enough for a proof. Thanks.
    __________________________________________________ ______________
    Question:
    Let F_0, F_1, F_2, ..... be the Fibonnaci numbers, defined by,

     F_0 = 1; F_1 = 1; F_n= F_{n-1} + F_{n-2}, for n \ge 2

    Prove that for all  n \ge 0 we have gcd(F_{n+2}, F_n) = 1

    __________________________________________________ _____________

    My attempts:
    I was considering two different methods to tackle this problem.
    __________________________________________________ _____________

    Method 1:
     F_{n+2} = F_n + F_{n+1}

    Using Euclid's algorithm, we find that the remainder when  F_{n+2} is divided by F_n is  F_{n+1}

    And Euclidean algorithm says that for integers such that:
     a = bq + r ,  gcd(a,b)=gcd(b,r)

    In this scenario,  a = F_{n+2}, b = F_n, c = F_{n+1} , which gives q=1.

    Hence  gcd(F_{n+2}, F_n) = gcd(F_n,F_{n+1})
    When n=0, gcd(F_0, F_1) = gcd(1,1) =  gcd(F_{n+2},F_n) = 1
    \Box

    __________________________________________________ ______________

    Method 2:
    Proceed by Induction. I won't bother posting my attempt for this yet, since if I can prove this without induction (i.e. like above) then there isn't much need in a longer proof - unless of course the first one isn't formal enough.

    __________________________________________________ ______________

    My question:
    Is method 1 a satisfactory proof? Are there any ways I can improve it?

    Thanks a lot fellas.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by WWTL@WHL View Post
    Method 1:
     F_{n+2} = F_n + F_{n+1}

    Using Euclid's algorithm, we find that the remainder when  F_{n+2} is divided by F_n is  F_{n+1}

    Using Euclid's algorithm, we find that the remainder when  F_{n+2} is divided by F_{n+1} is  F_{n}

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2007
    Posts
    127
    Quote Originally Posted by CaptainBlack View Post
    Using Euclid's algorithm, we find that the remainder when  F_{n+2} is divided by F_{n+1} is  F_{n}

    RonL
    Right, so now I'm realy stuck. Any ideas on what to do?

    EDIT:

    We can write  F_{n+1} = F_{n+2} - F_n

    so in Euclid's algorithm, the general form of  a = bq+r stands with  a = F_{n+1} ,  b = F_{n+2} ,  r = - F_n . It follows that q=1.

    So  gcd(F_{n+1}, F_{n+2}) = gcd(F_{n+2}, F_n)

    And gcd(F_{n+1}, F_{n+2}) , for n=0, is gcd(1,2) = 1.

    So  gcd(F_{n+2}, F_n) = 1

    But that can't be right because it seems that the remainder  - F_n made no difference to the outcome. i.e. it might as well have been positive.
    Last edited by WWTL@WHL; November 25th 2007 at 09:32 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fibonacci Numbers Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 13th 2011, 09:32 PM
  2. Proof about Fibonacci and Lucas numbers (GCD)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 21st 2010, 09:26 AM
  3. Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 30th 2010, 04:51 AM
  4. Induction Proof- Fibonacci Numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 18th 2010, 06:28 AM
  5. Proving Lucas Numbers and Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 18th 2008, 11:33 PM

Search Tags


/mathhelpforum @mathhelpforum