How to prove $\left|\sqrt{2} - \frac{m}{n}\right| > \frac{1}{3n^2}$ inductively? [duplicate]

I saw a problem online (Orig) as follows. I'm curious if there's a straightfoward way to prove it using induction.

It's easy to prove that (Orig) holds when $$n=1$$ or $$m=1$$ , which seems like a good way to set up base cases, but I'm stuck on where to go from there.

For all positive integers $$m, n$$, show that the following inequality (Orig) holds:

$$\left|\sqrt{2} - \frac{m}{n}\right| > \frac{1}{3n^2} \tag{Orig}$$

Note that (Orig) is equivalent to (201) below, because the LHS is irrational and the RHS is rational:

$$\left|\sqrt{2} - \frac{m}{n}\right| \ge \frac{1}{3n^2} \tag{201}$$

I suspect there's probably a general result about best rational approximations to an irrational number like $$\sqrt{2}$$ or something using the convergents of the continued fraction representation of $$\sqrt{2}$$ (101) . (Orig) feels like a statement of how well you can approximate $$\sqrt{2}$$ with rational numbers, but I don't know whether the $$\frac{1}{3n^2}$$ bound is tight or not.

$$\sqrt{2} = 1 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \cdots}}}} \tag{101}$$

I have some base cases as follows, $$n=m=1$$ (102); $$n=1, m > 1$$ (109); $$n>1, m=1$$ (117).

$$\left| \sqrt{2} - \frac{m}{n} \right| \ge \frac{1}{3n^2} \;\;\;\text{when n = m = 1} \tag{102}$$

And the proof of (102).

$$\left| \sqrt{2} - 1 \right | < \frac{1}{3} \tag{NG1}$$ $$\sqrt{2} - 1 < \frac{1}{3} \tag{104}$$ $$\sqrt{2} < \frac{4}{3} \tag{105}$$ $$4 < \frac{16}{9} \tag{106}$$ $$36 < 16 \tag{107}$$ $$\bot \tag{108}$$

And the next case (109)

$$\left| \sqrt{2} - \frac{m}{n} \right| \ge \frac{1}{3n^2} \;\;\;\text{when n = 1, m \ge 2} \tag{109}$$

The expression inside the absolute value on the LHS of (109) is always negative (NG2).

$$m - \sqrt{2} < \frac{1}{3} \tag{NG2}$$ $$m < \frac{1}{3} + \sqrt{2} \tag{111}$$

We know that $$2 \le m$$, so we can infer the following.

$$2 < \frac{1}{3} + \sqrt{2} \tag{112}$$

$$6 < 1 + 3\sqrt{2} \tag{113}$$

$$5 < 3\sqrt{2} \tag{114}$$

$$25 < 18 \tag{115}$$

$$\bot \tag{116}$$

And the next case (117)

$$\left| \sqrt{2} - \frac{1}{n} \right| \ge \frac{1}{3n} \;\;\;\text{where m = 1, n \ge 2} \tag{117}$$

$$\frac{1}{n}$$ is at most one, so the expression inside the absolute value on the LHS is positive.

$$\sqrt{2} - \frac{1}{n} < \frac{1}{3n} \tag{NG3}$$

$$\sqrt{2} < \frac{1}{3n} + \frac{1}{n} \tag{119}$$

$$\sqrt{2} < \frac{4}{3n} \tag{120}$$

$$3n\sqrt{2} < 4 \tag{121}$$

$$3n < 2 \sqrt{2} \tag{122}$$

$$9n^2 < 8 \tag{123}$$

however, $$n \ge 2$$ by hypothesis.

$$36 < 8 \tag{124}$$

$$\bot \tag{125}$$

marked as duplicate by Martin R, Community♦May 18 at 16:00

Because $$\sqrt2$$ is irrational, $$2n^2-m^2\ge1$$ or $$2n^2-m^2\le-1.$$ In the first case,

$$(\sqrt2n-m)(\sqrt2n+m)\ge 1,$$

so $$\sqrt2-\dfrac mn\ge\dfrac1{n(\sqrt 2 n+m)} \ge\dfrac 1 {n(\sqrt2n+\sqrt2n)}\ge\dfrac1{2\sqrt2 n^2}\ge\dfrac1{3n^2}.$$

In the second case, $$m^2-2n^2\ge1,$$ so $$(m-\sqrt2n)(m+\sqrt2n)\ge1,$$ so $$\dfrac mn-\sqrt2\ge\dfrac1{n(m+\sqrt2n)}.$$

Now if $$m\le\dfrac32n$$, then $$m+\sqrt2n<2m\le3n$$, so $$|\sqrt2-\frac mn|=\frac mn - \sqrt2\ge\dfrac1{n(m+\sqrt2 n)}\ge\dfrac1{n(3n)}=\dfrac1{3n^2}.$$

On the other hand, if $$m>\dfrac32n$$, then either $$n=1$$, in which case $$|m-\sqrt2|\ge\sqrt2-1>\dfrac1{3\times1^2}$$,

or $$n\ge2$$, in which case $$\dfrac mn-\sqrt2>\dfrac32-\sqrt2>\dfrac1{3\times2^2}\ge\dfrac1{3 n^2}.$$

• The 2nd case would imply $m<n\sqrt{2}$, which is wrong given $2n^2-m^2\leq -1<0$, right? – rtybase May 17 at 22:51
• @rtybase: please see my edited answer – J. W. Tanner May 19 at 14:15

In style to the Liouville's theorem mentioned in the comments, $$\sqrt{2}$$ is a root of $$P_2(x)=x^2-2$$. Then, for any $$\frac{m}{n}$$ we have an $$\varepsilon$$ in between $$\sqrt{2}$$ and $$\frac{m}{n}$$ such that (this is MVT) $$\left|P_2\left(\frac{m}{n}\right)\right|= \left|P_2(\sqrt{2})-P_2\left(\frac{m}{n}\right)\right|= |P_2'(\varepsilon)|\cdot \left|\sqrt{2}-\frac{m}{n}\right|$$ or $$\left|\sqrt{2}-\frac{m}{n}\right|= \left|\frac{m^2-2n^2}{2\varepsilon \cdot n^2}\right|\geq \frac{1}{2\left|\varepsilon\right| \cdot n^2}\tag{1}$$

Now, if $$\frac{m}{n}<\varepsilon<\sqrt{2}$$ then $$(1)$$ becomes $$\frac{1}{2\left|\varepsilon\right| \cdot n^2}>\frac{1}{2\sqrt{2}n^2}>\frac{1}{3n^2}$$ and we are done.

If $$\sqrt{2}<\varepsilon<\frac{m}{n}<\frac{3}{2}$$ then $$2\varepsilon<3$$ and $$(1)$$ becomes $$\frac{1}{2\left|\varepsilon\right| \cdot n^2}>\frac{1}{3n^2}$$. So, we are done.

If $$\sqrt{2}<\frac{3}{2}<\varepsilon<\frac{m}{n}$$ then $$\left|\frac{m}{n}-\sqrt{2}\right|> \left|\frac{3}{2}-\sqrt{2}\right|= \frac{\frac{9}{4}-2}{\frac{3}{2}+\sqrt{2}}= \frac{1}{2\cdot(3+ 2\sqrt{2})}> \frac{1}{3\cdot 2^2}\geq \frac{1}{3\cdot n^2}$$ for all $$n\geq2$$. For $$n=1$$ we have a trivial case $$m-\sqrt{2}\geq 2-\sqrt{2}>\frac{1}{3}$$.

• I think you should leave out $\dfrac1{4\cdot2\sqrt2},$ because that's not true, but the rest of the argument is fine – J. W. Tanner May 19 at 14:25
• @J.W.Tanner oops, indeed! Fixed, thank you for pointing out. – rtybase May 19 at 14:34

For any non-square $$d$$, $$1 \le|m^2-nd^2| =(m+n\sqrt{d})|m-\sqrt{d}|$$ so, dividing by $$n^2$$, $$\dfrac1{n^2} \le(\dfrac{m}{n}+\sqrt{d})|\dfrac{m}{n}-\sqrt{d}|$$ so $$|\dfrac{m}{n}-\sqrt{d}| \ge \dfrac1{n^2(\dfrac{m}{n}+\sqrt{d})}$$.

If this is an iteration such that $$m^2-dn^2 = 1$$, then $$\dfrac{m^2}{n^2} =d+\dfrac1{n^2}$$ so

$$\begin{array}\\ \dfrac{m}{n} &= \sqrt{d+\dfrac1{n^2}}\\ &= \sqrt{d}\sqrt{1+\dfrac1{dn^2}}\\ &\lt \sqrt{d}(1+\dfrac1{2dn^2}) \qquad\text{since }\sqrt{1+x} < 1+x/2\\ &= \sqrt{d}+\dfrac1{2n^2\sqrt{d}} \end{array}$$

so $$\dfrac{m}{n}+\sqrt{d} \lt 2\sqrt{d}+\dfrac1{2n^2\sqrt{d}}$$ so

$$\begin{array}\\ |\dfrac{m}{n}-\sqrt{d}| &\ge \dfrac1{n^2(2\sqrt{d}+\dfrac1{2n^2\sqrt{d}})}\\ &= \dfrac1{2n^2\sqrt{d}(1+\dfrac1{4n^2d})}\\ \end{array}$$

For $$d=2$$ this is $$|\dfrac{m}{n}-\sqrt{2}| \ge \dfrac1{2n^2\sqrt{2}(1+\dfrac1{8n^2})}$$.

So we want $$2\sqrt{2}(1+\dfrac1{8n^2}) \lt 3$$ or $$\dfrac{2\sqrt{2}}{8n^2} \lt 3-2\sqrt{2}$$ or $$n^2 \gt \dfrac{\sqrt{2}}{4(3-2\sqrt{2})} = \dfrac{\sqrt{2}(3+2\sqrt{2})}{4} \approx 2.06$$ so this holds for $$n \ge 2$$.

• In the first line, I think you meant $m-\color{red}n\sqrt d$ – J. W. Tanner May 19 at 14:27