# Hint Needed: Proving $\sqrt{2}$ is irrational using induction

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.

• 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. – Bill Dubuque Jan 25 at 14:44
• 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(?) – B. Goddard Jan 25 at 18:46
• @B. Goddard I have not heard of the well-ordering proof. Can you elaborate? – Naman Kumar Jan 26 at 2:47
• – 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.