Results 1 to 2 of 2

Thread: GCD and Fibonacci

  1. #1
    Apr 2010

    GCD and Fibonacci

    I am having a lot of trouble figuring this problem out. Any help would be appreciated.
    We can define a generalized Fibonacci sequence F1, F2, F3, F4, by first selecting four integers a, b, c, and e, and then letting F1=a, F2=b, and Fn=cFn-1+eFn-2 if n>2.
    a) Prove that, if d=gcd(a,b), then d|Fn for all n>=1.
    b) Prove that, if f=gcd(Fm, Fm-1) and gcd(f, e)=1 then f|d.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Mar 2010
    You prove (a) by induction. First show that it is true for n=1 and n=2, then show that if it is true for n=m-1 and n=m-2, then it must be true for n=m.

    You also prove (b) by induction. It is trivially true for m=2. If it is true for some m, that is the statement "if f=gcd(Fm, Fm-1) and gcd(f,e)=1, then f|d" is true, then if f=gcd(Fm+1,Fm) and gcd(f,e)=1, f=gcd(cFm+eFm-1,Fm) and use the properties of gcd to show f=gcd(Fm, Fm-1) and therefore f|d. So the statement is true for m+1.

    Post again in this thread if you're still having trouble.

    - Hollywood
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fibonacci
    Posted in the Math Puzzles Forum
    Replies: 6
    Last Post: May 15th 2011, 11:17 PM
  2. fibonacci
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Feb 4th 2010, 01:11 PM
  3. Fibonacci
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Sep 15th 2009, 03:50 PM
  4. Fibonacci
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Jan 25th 2009, 01:31 PM
  5. Fibonacci
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Dec 4th 2008, 06:04 PM

Search tags for this page

Click on a term to search for related topics.

Search Tags

/mathhelpforum @mathhelpforum