I came across this question in the book Challenge and Thrill of Pre-College Mathematics:

Prove that $\sqrt{2}$ is irrational using induction.

Apart from the fact that this is hardly the usual method for proving this, I have no idea even how to begin. What am I supposed to used induction on?

I suspected that I might use induction to attempt to prove that the decimal places of the expansion of $\sqrt{2}$ do not repeat themselves, but even that seems to elude me. Perhaps we can use induction to prove that there does not exist any rational number which can be $\sqrt{2}$?

Since I am fairly inexperienced in number theory (I'm currently self studying it in high school) please keep in mind that I know only very basic theory such as some prime theory, modular arithmetic and basic properties of the GCD, etc. I would also ask you to refrain from giving a detailed solution; I would prefer a hint with which I can complete the proof.

  • 1
    $\begingroup$ I have reopened this question because the proposed duplicate has only a single answer, yet there are many ways to interpret such proofs "by induction", and it is instructive to know more than one. $\endgroup$ – Bill Dubuque Jan 25 at 14:44
  • $\begingroup$ There's an alternative proof that $\sqrt{2}$ is irrational which uses well-ordering. Since well-ordering is equivalent to induction, perhaps these two proof could be patched together to get what you want(?) $\endgroup$ – B. Goddard Jan 25 at 18:46
  • $\begingroup$ @B. Goddard I have not heard of the well-ordering proof. Can you elaborate? $\endgroup$ – Naman Kumar Jan 26 at 2:47
  • $\begingroup$ See math.stackexchange.com/q/1965080/362009 $\endgroup$ – B. Goddard Jan 26 at 3:40

You may or may not be familiar with the typical proof by contradiction, which goes something like this: Assume $\sqrt{2} = \frac{a}{b}$ in lowest terms (i.e. with $\text{gcd}(a,b) = 1$). Square both sides to give $2b^2 = a^2$. Note that $2|LHS$, so $2|RHS$, which implies that $2|a$. However, 2 must also divide $b$. (Can you see why?) This contradicts the assumption that $\frac{a}{b}$ was in lowest terms.

If you drop the assumption that $\frac{a}{b}$ was in lowest terms, you can still achieve a contradiction using induction. Specifically, you can start with the equation $2b^2 = a^2$ and prove the statement "$2^k|a$ for all $k \in \mathbb{N}$” using induction on $k$. This makes it impossible for $a$ to be finite.

  • $\begingroup$ This is a very interesting way of proving it. Thanks! $\endgroup$ – Naman Kumar Jan 26 at 2:48

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.