The square root of 2
A rich proof of the irrationality of the square root of 2

Becoming sufficiently familiar with something is a substitute for understanding it.

John Conway

We have been told since high school that the square root of 2, is an irrational number, that is, \(\sqrt{2}\neq\frac{p}{q}\) for any integers \(p,q\). In the following, I layout an interesting proof of this attributed to John Conway, and inspired from this video. The proof is rich in that it can be extended to square roots of all whole numbers without a lot of effort, and also provides us an algorithm to compute the approximate square root of 2.

1   Powers of \(\sqrt{2}-1\)

The proof starts with observing two facts (or premises), and then performing logical inference from them to infer a conditional statement of the form \(Q\implies S\). We start with the closest integer approximation of \(\sqrt{2}\), which is \(1\) and look at the error \(e=\sqrt{2}-1\). Since \(1\) is the closest integer to \(\sqrt{2}\), it follows that \(\lvert e\rvert=\lvert\sqrt{2}-1\rvert\le 1\). This means that the powers of \(e\) will converge to \(0\), that is \(e^1,e^2,e^3,\dotsc\) is a sequence of numbers that get smaller and smaller in magnitude, and closer and closer to \(0\).

In fact according to the definition of convergence, they get arbitrarily close to \(0\). This means that for any arbitrary threshold \(\varepsilon\gt 0\), there is a number \(N\), such that \(\lvert e^n-0\rvert \lt \varepsilon\) when \(n\gt N\).

This is the first fact, the first premise, \(P_1\), that we can get arbitrarily close to \(0\) by taking powers of \(e\).

2   The expansion of the powers of \(\sqrt{2}-1\)

We can prove using induction that any whole power of \(e\), that is \((\sqrt{2}-1)^n\) for any \(n\in\mathbb{N}\), can be represented as \(a\sqrt{2}+b\) for \(a,b\in\mathbb{Z}\). Let's just do that.

We know that for \((\sqrt{2}-1)^1\), we can write it with \(a=1\) and \(b=-1\).

Let \(P(n):\) There exist some integers \(a\) and \(b\) such that \((\sqrt{2}-1)^n=a\sqrt{2}+b\). We want to prove that \(P(n)\implies P(n+1)\).

This can be easily proved by assuming we have the two integers \(a\) and \(b\) such that \(e^n=a\sqrt{2}+b\) and noting that \((\sqrt{2}-1)^{n+1}=(a\sqrt{2}+b)(\sqrt{2}-1)\). Expanding this gives \(e^{n+1}=2a-a\sqrt{2}+b\sqrt{2}-b\) which can be rewritten as \((b-a)\sqrt{2}+(2a-b)\). And from the fact that integers are a group, it follows that both \(a'=b-a\) and \(b'=2a-b\) are also integers.

As an aside, note that this gives us a method to approximate the value of \(\sqrt{2}\). We know that \(e^n\) converges to \(0\). So, we can compute \(\sqrt{2}\) approximately by setting \(a\sqrt{2}+b=0\) and solving for \(\sqrt{2}\). But we will need the values of \(a\) and \(b\) for \(n\). This can be easily computed by setting \(a_1=1\) and \(b_1=-1\), and then computing \(a_n=b_{n-1}-a_{n-1}\) and \(b_n=2a_{n-1}-b_{n-1}\). Once we have it, our approximation is \(-\frac{b_n}{a_n}\). The error falls down exponentially with \(n\) because we are using the approximation that \(e^n\approx 0\), and with each increment in \(n\), we decrease the error by one full exponent. We can compute the error \(\sqrt{2}-\frac{-b_n}{a_n}\) using previous estimates of \(\sqrt{2}\) as \(e=\left\lvert \frac{-b_n}{a_n} - \frac{-b_{n-1}}{a_{n-1}}\right\rvert\). But what's interesting is no matter what values of \(a\) and \(b\) you start with, the recursion will always converge to \(\sqrt{2}\). Can you find out why? (Hint)

In summary, the important thing to remember at this point is that this is our second premise, \(P_2\), that for any \(n\in\mathbb{N}\) we have integers \(a,b\in\mathbb{Z}\) such that \((\sqrt{2}-1)^n=a\sqrt{2}+b\).

3   If \(\sqrt{2}=\frac{p}{q}\)

Now, it's time to introduce our final premise, a premise whose truth we don't know. Such a premise is called a conditional premise \(Q\), and any conclusion \(S\) derived by adding such a premise to our existing premises is a conditional inference conditioned to the fact that the said premise is true. If you have premises \(P_1,P_2,\dotsc,P_n\), and with the addition of \(Q\) you can derive \(S\), then using rules of conditional inference, you have derived that \(Q\implies S\). This principle will be important. Note that this is also the principle used in mathematical induction.

The conditional premise \(Q\) that we will be adding is the assumption that \(\sqrt{2}=\frac{p}{q}\) for some integers \(p\) and \(q\). Note that if \(\sqrt{2}=\frac{p}{q}\), then we have $$e^n=a\sqrt{2}+b=a\frac{p}{q}+b \quad(\text{from }P_2)$$ which means that $$e^n=\frac{ap+bq}{q}.$$

From \(P_1\) we know that we can get arbitrarily close to \(0\) by computing powers of \(\sqrt{2}-1\). We will need a third premise, \(P_3\) that we haven't stated so far. \(P_3\) says that multiplies of a rational number \(1/q\) are equally spaced on the number line, and that there is nothing between \(0/q\) and \(1/q\) that is a multiple of \(1/q\). Similarly, there is nothing between \(-1/q\) and \(0/q\) that is a multiple of \(1/q\).

Now, the fact that \(e^n\) can get arbitrarily close to \(0\) implies that we will have a power of \(e\) that is closer to \(0\) than \(1/q\) or \(-1/q\). But, using \(P_2\) and \(Q\), we showed that all powers of \(e\) are multiples of \(1/q\). This means that we will exclude all multiples of \(1/q\) that are \(\ge 1/q\) and also those that are \(\le -1/q\). This also means that there is a suffix of the sequence, \(\{e^m\}_{m\ge M}\) such that distances of its elements from \(0\) are \(\lt 1/q\), that is, all the elements of the sequence are the only remaining multiple of \(1/q\), which is \(0/q=0\). So, for some \(n\), we have \(e^n=(\sqrt{2}-1)^n=0\).

This implies that \(\sqrt{2}-1=0\) or that \(\sqrt{2}=1\). Our conclusion statement \(S\) is that \(\sqrt{2}\) is an integer.

Thus, using the principle of conditional inference, we have proved the implication \(Q\implies S\), that is, if \(\sqrt{2}\) is rational, then \(\sqrt{2}\) is an integer. We will be using the contrapositive of this, that is \(\lnot S\implies\lnot Q\).

We know, for a fact, that \(\sqrt{2}\) is not an integer, because \(1^2\lt 2\lt 2^2\) and the function \(\sqrt{x}\) is monotonically increasing on \(\mathbb{Z}_+\). Thus the square root of 2 is not rational.

4   Extending beyond 2

The method of proof that we went through can be adapted for any \(x\in\mathbb{Z}_+\). There will always be an integer closest to \(\sqrt{x}\). We don't even need to know its value, we can just call it \(A\), and go on with the proof. In the end, just like we proved that \(\sqrt{2}=1\), we can prove that \(\sqrt{x}=A\), and thus \(\sqrt{x}\) is an integer if it is rational.

The more profound fact is that the only rational square roots are integers.