무한 연분수와 최선의 근사Infinite Continued Fractions and Best Approximations

Recursion. For convenience define $p_{-2} = 0, q_{-2} = 1, p_{-1} = 1, q_{-1} = 0$, and for $0 \le k \le n$ set

We prove by induction on $k$ that $p_k, q_k$ defined this way satisfy $C_k := [a_0;a_1,\cdots,a_k] = \frac{p_k}{q_k}$ $(0 \le k \le n)$.

$k = 0, 1, 2$. A direct computation gives $p_0 = a_0 \cdot 1 + 0 = a_0$, $q_0 = a_0 \cdot 0 + 1 = 1$, so $C_0 = [a_0] = a_0 = \frac{p_0}{q_0}$. Also $p_1 = a_1a_0 + 1$, $q_1 = a_1$, so $C_1 = [a_0;a_1] = a_0 + \frac{1}{a_1} = \frac{a_1a_0+1}{a_1} = \frac{p_1}{q_1}$. And $p_2 = a_2p_1 + p_0 = a_2(a_1a_0+1) + a_0$, $q_2 = a_2q_1 + q_0 = a_2a_1 + 1$, so

Hence the statement holds for $k = 0, 1, 2$.

Inductive step. The computations for $k = 1, 2$ above never used that the last entry is an integer, so they stay valid with that entry replaced by an arbitrary real $t \gt 0$: indeed $[a_0;t] = a_0 + \frac1t = \frac{ta_0+1}{t} = \frac{tp_0+p_{-1}}{tq_0+q_{-1}}$ and $[a_0;a_1,t] = a_0 + \cfrac{1}{a_1+\frac1t} = \frac{t(a_1a_0+1)+a_0}{ta_1+1} = \frac{tp_1+p_0}{tq_1+q_0}$. We therefore take the induction hypothesis in the stronger form with a real last entry: for some $2 \le m \lt n$ assume that, for every real $t \gt 0$, $[a_0;a_1,\cdots,a_{m-1},t] = \frac{tp_{m-1}+p_{m-2}}{tq_{m-1}+q_{m-2}}$ $(\ast_m)$ (taking $t = a_m$ gives $C_m = \frac{p_m}{q_m}$). For every real $t \gt 0$ we have $[a_0;\cdots,a_m,t] = \left[a_0;\cdots,a_{m-1},a_m + \frac{1}{t}\right]$ with $a_m + \frac1t \gt 0$, so applying $(\ast_m)$ at $a_m + \frac1t$ gives

which is $(\ast_{m+1})$. In particular, taking $t = a_{m+1}$ gives $C_{m+1} = [a_0;\cdots,a_m,a_{m+1}] = \frac{a_{m+1}p_m + p_{m-1}}{a_{m+1}q_m + q_{m-1}} = \frac{p_{m+1}}{q_{m+1}}$, so the statement also holds for $k = m+1$. Therefore $[a_0;a_1,\cdots,a_k] = \frac{p_k}{q_k}$ for all $0 \le k \le n$.

1. Let $x = [\overline{2;3}] = [2;3,2,3,\cdots]$, so $x = 2 + \cfrac{1}{3 + \cfrac{1}{x}}$. Let $u = 3 + \frac{1}{x} = \frac{3x+1}{x}$; since $x = 2 + \frac{1}{u}$ gives $u = \frac{1}{x-2}$,

By the quadratic formula,

Since $x = [2;3,2,3,\cdots] \gt 2 \gt 0$, we discard the negative root $\frac{3-\sqrt{15}}{3} (\approx -0.29)$ and take the positive one,

2. Let $x = [2; \overline{1,2,1}] = [2;1,2,1,1,2,1,\cdots]$. Setting $y = [\overline{1;2,1}] = [1;2,1,\overline{1,2,1}] = [1;2,1,y]$ gives $x = 2 + \frac{1}{y}$. Unwinding $y = [1;2,1,y]$ from the inside,

so $y(3y+2) = 4y+3$, i.e. $3y^2 - 2y - 3 = 0$. By the quadratic formula,

and since $y = [1;2,1,\cdots] \gt 1 \gt 0$, we take the positive root $y = \frac{1+\sqrt{10}}{3} \ (\approx 1.38743)$. Therefore

In all three cases we simply run the algorithm for computing a simple continued fraction. Following its notation, put $x_0 = x$, $a_m = [x_m]$, $\xi_m = x_m - a_m$, $x_{m+1} = \frac{1}{\xi_m}$.

Preliminaries. For $n \in \mathbb{Z}_{\gt 0}$,

(here $2 \le 2n$ because $n \ge 1$). Hence $n^2+1,\ n^2+2,\ n^2+2n$ all lie strictly between the consecutive squares $n^2$ and $(n+1)^2$, so none of them is a perfect square and all three square roots are irrational. Consequently $\xi_m = 0$ never occurs, so the algorithm never terminates and produces an infinite simple continued fraction. The same inequalities give, in all three cases,

so that $a_0 = n$ every time.

1. With $x_0 = \sqrt{n^2+1}$ and $a_0 = n$ we get $\xi_0 = \sqrt{n^2+1} - n$ and

Adding $n$ to $n \lt \sqrt{n^2+1} \lt n+1$ gives $2n \lt x_1 \lt 2n+1$, so $a_1 = 2n$. Then

The algorithm returns to the state $x_1$, so by induction $x_m = x_1$ and $a_m = 2n$ for every $m \ge 1$. Therefore

2. With $x_0 = \sqrt{n^2+2}$ and $a_0 = n$,

From $\sqrt{n^2+2} \gt n$ we get $x_1 \gt \frac{n+n}{2} = n$, and from $n^2+2 \lt n^2+4n+4 = (n+2)^2$ we get $\sqrt{n^2+2} \lt n+2$, hence $x_1 \lt \frac{(n+2)+n}{2} = n+1$. So $n \lt x_1 \lt n+1$, i.e. $a_1 = n$, and

Since $n \lt \sqrt{n^2+2} \lt n+1$ we have $2n \lt x_2 \lt 2n+1$, i.e. $a_2 = 2n$, and

Thus $x_{m+2} = x_m$ for $m \ge 1$ and the partial quotients repeat $n, 2n$. Therefore

3. With $x_0 = \sqrt{n^2+2n}$ and $a_0 = n$,

From $\sqrt{n^2+2n} \gt n$ we get $x_1 \gt \frac{n+n}{2n} = 1$; and for $n \ge 1$ we have $n^2+2n \lt 9n^2$ (i.e. $2n \lt 8n^2$, i.e. $1 \lt 4n$), so $\sqrt{n^2+2n} \lt 3n$ and $x_1 \lt \frac{3n+n}{2n} = 2$. So $1 \lt x_1 \lt 2$, i.e. $a_1 = 1$, and

Since $n \lt \sqrt{n^2+2n} \lt n+1$ we have $2n \lt x_2 \lt 2n+1$, i.e. $a_2 = 2n$, and

So the partial quotients repeat $1, 2n$, and therefore

In each case the sequence of partial quotients produced by the algorithm is the simple continued fraction expansion of the number, and since all three numbers are irrational, the passage on p.28 gives $x = \lim_{n \to \infty}[a_0;a_1,\cdots,a_n]$. Hence the periodic continued fractions obtained above are exactly the required expansions. (Theorem 3.20 states uniqueness for finite simple continued fractions, so it does not apply directly here.)

Check. For $n = 1$, part 1 gives $\sqrt2 = [1;\overline2]$ (agreeing with Example 3.32); for $n = 2$, part 2 gives $\sqrt6 = [2;\overline{2,4}]$; for $n = 3$, part 3 gives $\sqrt{15} = [3;\overline{1,6}]$.

The partial quotients of the given infinite simple continued fraction are $a_0 = 1$ and, for $j \ge 1$, $a_{2j-1} = 2j+1$, $a_{2j} = 1$; that is,

Computing the convergents by the recursion $p_k = a_kp_{k-1}+p_{k-2}$, $q_k = a_kq_{k-1}+q_{k-2}$ (with $p_{-1}=1, q_{-1}=0, p_{-2}=0, q_{-2}=1$) gives:

For instance $p_3 = 5\cdot5 + 4 = 29$, $q_3 = 5\cdot4+3 = 23$, and $p_6 = 1\cdot267 + 34 = 301$, $q_6 = 1\cdot212+27 = 239$.

How Theorem 3.31 is used. Writing $x = [a_0;a_1,\cdots,a_n]$, here $n = \infty$, so every $m$ satisfies $m \lt n$. By Theorem 3.31, for every integer $b$ with $1 \le b \le q_m$ and every integer $a$,

that is, no rational number with denominator at most $q_m$ is closer to $x$ than the convergent $\frac{p_m}{q_m}$. Hence whenever the prescribed bound on the denominator is exactly some $q_m$, that convergent $\frac{p_m}{q_m}$ is the required best approximation.

1. The table gives $q_3 = 23$. Applying Theorem 3.31 with $m = 3$: for every rational $\frac ab$ with $1 \le b \le 23$ we have $\left|x - \frac{29}{23}\right| \le \left|x - \frac ab\right|$. So the best approximation is

(Note $q_4 = 27 \gt 23$, so $\frac{29}{23}$ is the last convergent whose denominator is at most $23$; and by Theorem 3.30, $\left|x - \frac{29}{23}\right| \lt \frac{1}{q_3q_4} = \frac{1}{621}$.)

2. The table gives $q_6 = 239$. Applying Theorem 3.31 with $m = 6$: for every rational $\frac ab$ with $1 \le b \le 239$ we have $\left|x - \frac{301}{239}\right| \le \left|x - \frac ab\right|$. So the best approximation is

(Again $q_7 = 2363 \gt 239$, so $\frac{301}{239}$ is the last convergent whose denominator is at most $239$, and by Theorem 3.30, $\left|x - \frac{301}{239}\right| \lt \frac{1}{q_6q_7} = \frac{1}{564757}$.)

Check. $x = 1.2594158\cdots$, while $\frac{29}{23} = 1.2608695\cdots$ and $\frac{301}{239} = 1.2594142\cdots$, so the errors are about $1.45 \times 10^{-3}$ and $1.62 \times 10^{-6}$ respectively.

Note. Item 1 of the printed statement writes the fraction as $\frac{q}{p}$, while the hint and the text (Theorem 3.30) write a convergent with numerator $p_n$ and denominator $q_n$. Below we follow the convention of the text and write the approximation as $\frac{p}{q}$ (numerator $p$, denominator $q$).

The expansion and its convergents. Since $15 = 3^2 + 2\cdot3$, Exercise 3.26 part 3 with $n = 3$ gives

The recursion $p_k = a_kp_{k-1}+p_{k-2}$, $q_k = a_kq_{k-1}+q_{k-2}$ gives the convergents:

1. By the hint (Theorem 3.30), $\left|\sqrt{15} - \frac{p_m}{q_m}\right| \lt \frac{1}{q_mq_{m+1}}$, so it suffices that $q_mq_{m+1} \ge 50^2 = 2500$ in order to get $\left|\sqrt{15} - \frac{p_m}{q_m}\right| \lt \frac{1}{2500}$. From the table,

so $m = 4$ is the first index that works. Therefore

Check. $\sqrt{15} = 3.8729833\cdots$ and $\frac{213}{55} = 3.8727272\cdots$, so the error is about $2.56 \times 10^{-4}$, less than $\frac{1}{2500} = 4 \times 10^{-4}$.

2. Approximating to four decimal places means that the value rounded to four decimals agrees with that of $\sqrt{15}$, for which an error smaller than $\frac{1}{2} \times 10^{-4} = 5 \times 10^{-5} = \frac{1}{20000}$ is enough. Using Theorem 3.30 again, it suffices that $q_mq_{m+1} \ge 20000$, and from the table

so $m = 5$ is the first index that works. Hence the required convergent is

Check. $\sqrt{15} = 3.87298334\cdots$ and $\frac{244}{63} = 3.87301587\cdots$, so the error is about $3.25 \times 10^{-5}$, and rounding both numbers to four decimals gives $3.8730$ in each case.

Note. If "agreeing to four decimal places" is read strictly as the first four decimal digits coinciding without rounding, then $\sqrt{15} = 3.8729\cdots$ while $\frac{244}{63} = 3.8730\cdots$, so $\frac{244}{63}$ would not qualify; under that reading the answer is the next convergent $\frac{1677}{433} = 3.872979\cdots$ (error about $4.13 \times 10^{-6}$). We take the usual reading with rounding and give $\frac{244}{63}$ as the answer.

Write $y = \frac{1+\sqrt{10}}{3}$.

1. The inequality $\left|y - \frac{18}{13}\right| \lt \frac{1}{2 \cdot 13^2}$. Putting the difference over a common denominator,

Since $13\sqrt{10} = \sqrt{1690}$ and $41 = \sqrt{1681}$ with $1681 \lt 1690$, we get $13\sqrt{10} \gt 41$, so the quantity above is positive and the absolute value may be dropped. Multiplying by the conjugate,

From $10 \gt 9$ we get $\sqrt{10} \gt 3$, hence $13\sqrt{10} + 41 \gt 39 + 41 = 80$ and therefore

Consequently

and since $3 \cdot 338 = 1014 \lt 1040$ we have $\frac{3}{1040} \lt \frac{1}{338} = \frac{1}{2 \cdot 13^2}$. Chaining the two inequalities,

(Numerically $\left|y - \frac{18}{13}\right| = 0.0028105\cdots \lt \frac{3}{1040} = 0.0028846\cdots \lt \frac{1}{338} = 0.0029585\cdots$.)

2. $\frac{18}{13}$ is a convergent to $y$. Run the algorithm for computing a simple continued fraction. In its notation put $x_0 = y$, $a_m = [x_m]$, $\xi_m = x_m - a_m$, $x_{m+1} = \frac{1}{\xi_m}$.

From $9 \lt 10 \lt 16$ we get $3 \lt \sqrt{10} \lt 4$, so $\frac{4}{3} \lt y \lt \frac{5}{3}$; in particular $1 \lt y \lt 2$ and $a_0 = 1$. Then $\xi_0 = y - 1 = \frac{\sqrt{10}-2}{3}$, so

The same bounds give $\frac52 \lt x_1 \lt 3$, in particular $2 \lt x_1 \lt 3$, so $a_1 = 2$ and $\xi_1 = x_1 - 2 = \frac{\sqrt{10}-2}{2}$, whence

Again $\frac53 \lt x_2 \lt 2$, in particular $1 \lt x_2 \lt 2$, so $a_2 = 1$ and $\xi_2 = x_2 - 1 = \frac{\sqrt{10}-1}{3}$, whence

So after three steps the algorithm returns to its initial state: $x_{m+3} = x_m$ for all $m \ge 0$, and the partial quotients repeat $1, 2, 1$. Therefore

(This is exactly the conclusion $y = [1;2,1,y]$ found in Exercise 3.25 part 2. Also, $\sqrt{10}$ is irrational, so $\xi_m = 0$ never occurs and the expansion is infinite.)

Now compute the convergents by the recursion $p_k = a_kp_{k-1}+p_{k-2}$, $q_k = a_kq_{k-1}+q_{k-2}$ (with $p_{-1}=1, q_{-1}=0, p_{-2}=0, q_{-2}=1$).

For instance $p_4 = a_4p_3 + p_2 = 2 \cdot 7 + 4 = 18$ and $q_4 = a_4q_3 + q_2 = 2 \cdot 5 + 3 = 13$. Thus

so $\frac{18}{13}$ is the (fourth) convergent to $\frac{1+\sqrt{10}}{3}$.

Remark. Theorem 3.30 with $m = 4$ only yields $\left|y - \frac{18}{13}\right| \lt \frac{1}{q_4q_5} = \frac{1}{13 \cdot 18} = \frac{1}{234}$, which is weaker than $\frac{1}{2 \cdot 13^2} = \frac{1}{338}$. That is why part 1 was proved by the direct estimate above.