How do I prove that the square root of 2 is irrational using the principle of mathematical induction?
Prove that square root of 2 is irrational using the principle of Mathematical Induction
4
$\begingroup$
induction
rationality-testing
-
5See: http://www.mathpath.org/proof/sqrt.irrat.other.htm – 2012-08-17
-
0http://math.stackexchange.com/questions/917983/the-proof-of-sqrt2-is-not-rational-number-via-fundamental-theorem-of-arithm – 2015-11-20
2 Answers
2
The usual proof starts out something like "suppose for a contradiction $\sqrt 2$ were rational, and write it as $p/q$ in lowest terms ...".
The "in lowest terms" hides an instance of induction, which you can unfold to get a proof in the shape of
Theorem. For all positive integers $p$ and $q$, it holds that $(p/q)^2\ne 2$.
Proof. By long induction on $q$. If $p$ and $q$ have a common factor $n>1$ then $(\frac pq)^2 = (\frac{p/n}{q/n})^2$, and since $q/n
, the induction hypothesis guarantees that $(\frac pq)^2\ne 2$. Now we consider the case that $p$ and $q$ are relatively prime ...
-
0One can also find induction in the case p,q coprime. Induction is everywhere in proofs about naturals, so it's difficult (if not impossible) to classify proofs by induction or not. These elementary proofs of irrationality all essentially depend on the Division (Euclidean) algorithm, so the descent implied by such may be viewed as the inductive essence of the matter. But, pedagogically, the proofs are better presented with this induction encapsulated in a Lemma (Division algorithm), rather than directly inlining said lemma into proofs, only for the sake of "making the proof look inductive". – 2012-08-17
-
0Is "*long* induction" another name for strong induction? – 2012-08-17
-
0For a nontrivial example of a proof where such descent/induction has been "inlined" into a proof, see [Zermelo's classical proof of unique factorization of integers,](http://math.stackexchange.com/a/117416/242) where he has inlined the classical inductive/descent proof of the prime divisor property $\rm\:p\:|\:ab\:$ $\Rightarrow$ $\rm\:p\:|\:a\:$ or $\rm\:p\:|\:b.\ $ – 2012-08-17
-
0@JenniferDylan: Yes, they are synonyms. I learned it as long induction, but there are others who call it strong instead. – 2012-08-17
-1
This is as simple as I could make it in my mind, working on the simply basis of multiple factors (similar to the above) but less algebraic manipulation: