Fibonacci Proof

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

So I tried proving it with induction.

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

Using an identity I know and have proved,

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

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

Any hints?

Quote:

---

Originally Posted by redsoxfan325

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

So I tried proving it with induction.

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

Using an identity I know and have proved,

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

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

Any hints?

---

Hint: Do induction on 'q' rather than m. That should do it.

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

Quote:

---

Originally Posted by redsoxfan325

I can do that, but does that prove the same thing as induction on $\displaystyle m$? (Because the idea was supposed to be that $\displaystyle q$ is constant and $\displaystyle 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.

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

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.

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')