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.
Best Answer
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.