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

Question

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} $$

Answer 1

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}.$

Answer 2

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}$.

Answer 3

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$.