5
$\begingroup$

I have looked a bunch of solutions of this problem on the web. But I want to know that whether my solution is correct or not. My solution is as follows

Proof(By Induction)

$P(n)$:The Fibonacci numbers $F_n$ and $F_{n + 1}$ are relatively prime.

Base Case: $P(0)$ is true because $F_0 = 0$ and $F_1 = 1$ are relatively prime.

Inductive Step: Assume $P(n)$ to be true. Now to show that for $n \geq 0$, $P(n) \implies P(n + 1)$

$\implies \gcd(F_n, F_{n + 1}) = 1$

$\implies s(F_n) + t(F_{n + 1}) = 1$

$\implies s(F_{n + 2} - F_{n + 1}) + t(F_{n + 1}) = 1$

$\implies (t - s)(F_{n + 1}) + s(F_{n + 2}) = 1$

$\implies \gcd(F_{n + 1}, F_{n + 2}) = 1$

$\implies P(n + 1)$ is true

Thus, by induction $P(n)$ is true for all $n \geq 0$.

$\endgroup$
  • $\begingroup$ The basic idea is fine. You should say that there exist integers $s$ and $t$ such that $\dots$. $\endgroup$ – André Nicolas Jan 10 '15 at 3:14
  • $\begingroup$ You don't even need the $s$-$t$ argument for this, incidentally, if you have the basic fact (key to the Euclidean algorithm) that $\gcd(a,b)=\gcd(a,a+b)$. You can just say $\gcd(F_n, F_{n-1})=\gcd(F_n, F_n+F_{n-1})=\gcd(F_n, F_{n+1})$. $\endgroup$ – Steven Stadnicki Jan 10 '15 at 3:46
  • $\begingroup$ Here is an easier argument. Assume $F_{n}$ and $F_{n+1}$ are relatively prime. (This is clear when $n=0$, so we can take $n\geq 1$.) Let $d\geq 1$ be a common factor of $F_{n+1}$ and $F_{n+2}$. Then $d$ is a factor of $F_{n+2}-F_{n+1}=F_{n}$, so $d$ is a common factor of $F_{n}$ and $F_{n+1}$, which by the inductive hypothesis implies $d=1$. Thus $F_{n+1}$ and $F_{n+2}$ are relatively prime. (A more general result to prove: $\gcd(F_m,F_n) = F_{\gcd(m,n)}$.) $\endgroup$ – KCd Jan 10 '15 at 3:47
  • $\begingroup$ As others said, you must say “There exist integers $s$ and $t$ for which ...” You can’t conclude that $s(F_n) + t(F_{n + 1}) = 1$ otherwise, because $s$ and $t$ are meaningless symbols. You should also not simply connect everything with $\implies$ symbols. For example, you say $\implies\gcd(F_n,F_{n+1})=1$. What exactly implies what? You also need to conclude $P(n+1)$ or (better) conclude that $P(n)\implies P(n+1)$ in the inductive step. You have convinced the reader, but you should say it more clearly. You have a valid mathematical argument, but you need to present it a little bit better. $\endgroup$ – Steve Kass Jan 10 '15 at 4:24
4
$\begingroup$

The idea is fine, but you really ought to use more words; it makes the argument much clearer and much more readable. Here’s how I would present the same argument.

Assume as induction hypothesis that $\gcd(F_n,F_{n+1})=1$. Then there are integers $s$ and $t$ such that

$$\begin{align*} 1&=sF_n+tF_{n+1}\\ &=s(F_{n+2}-F_{n+1})+tF_{n+1}\\ &=sF_{n+2}+(t-s)F_{n+1}\;, \end{align*}$$

and it follows that $\gcd(F_{n+1},F_{n+2})=1$ as well. The result now follows by induction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.