Fibonacci Proof

Printable View

Nov 28th 2009, 09:54 PM
redsoxfan325

Fibonacci Proof

I hate to say this, but...I'm stuck on an induction proof. I'm trying to prove that $\gcd(F_m,F_n)=F_{\gcd(m,n)}$ , where $F_j$ is the $j$ th Fibonacci number. I have it reduced to proving that $F_m\,|\,F_{qm}$ for all $m$ . I have the rest of the proof.

So I tried proving it with induction.

It's trivial for $m=1$ , so I assumed $F_m\,|\,F_{qm}$ . Then I tried to prove that $F_{m+1}\,|\,F_{qm+q}$ .

Using an identity I know and have proved,

$F_{qm+q}=F_qF_{qm+1}+F_{q-1}F_{qm}=F_qF_{qm+1}+kF_{q-1}F_m$

for some $k\in\mathbb{N}$ , but now I'm stuck.

Any hints?
Nov 28th 2009, 10:00 PM
aman_cc

Quote:

Originally Posted by redsoxfan325

I hate to say this, but...I'm stuck on an induction proof. I'm trying to prove that $\gcd(F_m,F_n)=F_{\gcd(m,n)}$ , where $F_j$ is the $j$ th Fibonacci number. I have it reduced to proving that $F_m\,|\,F_{qm}$ for all $m$ . I have the rest of the proof.

So I tried proving it with induction.

It's trivial for $m=1$ , so I assumed $F_m\,|\,F_{qm}$ . Then I tried to prove that $F_{m+1}\,|\,F_{qm+q}$ .

Using an identity I know and have proved,

$F_{qm+q}=F_qF_{qm+1}+F_{q-1}F_{qm}=F_qF_{qm+1}+kF_{q-1}F_m$

for some $k\in\mathbb{N}$ , but now I'm stuck.

Any hints?

Hint: Do induction on 'q' rather than m. That should do it.
Nov 28th 2009, 10:08 PM
redsoxfan325

I can do that, but does that prove the same thing as induction on $m$ ? (Because the idea was supposed to be that $q$ is constant and $m$ is the variable.)
Nov 28th 2009, 10:13 PM
aman_cc

Quote:

Originally Posted by redsoxfan325

I can do that, but does that prove the same thing as induction on $m$ ? (Because the idea was supposed to be that $q$ is constant and $m$ is the variable.)

I guess you want to prove that the above is true for any +ve integers m,q

So you can induct on m and under the induction hypothesis prove it is true for all q.

Or you can induct on q and under the induction hypothesis prove it is true for all m.

If you think carefully both prove the original statement. Atleast I'm pretty convinced.

The reason to chose 2nd approach is that the result is closely tied to induction on q rather than induction on m. It's almost trivial that way.
Nov 28th 2009, 10:16 PM
aman_cc

Quote:

Originally Posted by aman_cc

I guess you want to prove that the above is true for any +ve integers m,q

So you can induct on m and under the induction hypothesis prove it is true for all q.

Or you can induct on q and under the induction hypothesis prove it is true for all m.

If you think carefully both prove the original statement. Atleast I'm pretty convinced.

The reason to chose 2nd approach is that the result is closely tied to induction on q rather than induction on m. It's almost trivial that way.

You may want to look at a similar post I did a few days ago -
http://www.mathhelpforum.com/math-he...tml#post410668

Your original problem follows directly from the identity, I wrote there. This is just FYI
Nov 28th 2009, 10:19 PM
redsoxfan325

Yes, I agree that the second method is quite easy. I'll think about this until I'm convinced that inducting on q gives the same result.
Nov 28th 2009, 10:21 PM
aman_cc

Quote:

Originally Posted by redsoxfan325

Yes, I agree that the second method is quite easy. I'll think about this until I'm convinced that inducting on q gives the same result.

Sure. I can help you prove that if you are not convinced. Please note the 'for all' in my post above. That would be critical in the proof I will give (for induction on 'q')