Thread: 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.

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