Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How do I prove that the square root of 2 is irrational using the principle of mathematical induction?

share|cite|improve this question
See: – Frenzy Li Aug 17 '12 at 13:17
up vote 1 down vote accepted

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<q$, the induction hypothesis guarantees that $(\frac pq)^2\ne 2$. Now we consider the case that $p$ and $q$ are relatively prime ...

share|cite|improve this answer
One 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". – Bill Dubuque Aug 17 '12 at 14:27
Is "long induction" another name for strong induction? – user2468 Aug 17 '12 at 14:29
For 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, 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.\ $ – Bill Dubuque Aug 17 '12 at 14:31
@JenniferDylan: Yes, they are synonyms. I learned it as long induction, but there are others who call it strong instead. – Henning Makholm Aug 17 '12 at 15:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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