유한 연분수Finite Continued Fractions

By Euclid’s algorithm, for $\frac{172}{51}$ we get

Reading off the quotients,

In the same way, for $\frac{71}{55}$ we get

so

By Euclid’s algorithm, we get

Since $\frac{118}{303} \lt 1$, $a_0 = 0$, and reading off the remaining quotients,

For $\left[-2; 2, 4, 6, 8\right]$, $a_0=-2, a_1=2, a_2=4, a_3=6, a_4=8$. Applying the recursion $p_k = a_kp_{k-1}+p_{k-2}$, $q_k = a_kq_{k-1}+q_{k-2}$ of Theorem 3.8 (with $p_{-2}=0, q_{-2}=1, p_{-1}=1, q_{-1}=0$),

By Theorem 3.8, $\left[-2; 2, 4, 6, 8\right] = C_4 = \frac{p_4}{q_4} = -\frac{710}{457}$, and by Corollary 3.10 this is already in lowest terms.

In the same way, for $\left[0; 1, 2, 3, 4, 3, 2, 1\right]$ we have $a_0=0, a_1=1, a_2=2, a_3=3, a_4=4, a_5=3, a_6=2, a_7=1$, so

so $\left[0; 1, 2, 3, 4, 3, 2, 1\right] = C_7 = \frac{p_7}{q_7} = \frac{321}{460}$, again in lowest terms by Corollary 3.10.

For $\left[1;2,3,\cdots,n,n+1\right]$ we have $a_k = k+1$ ($0 \le k \le n$), so the recursion of Theorem 3.8 reads $p_k = (k+1)p_{k-1}+p_{k-2}$ for all $k \ge 0$ (using the earlier convention $p_{-2}=0, p_{-1}=1$).

Step 1. Taking $k=n$, since $a_n=n+1$,

Step 2. For each $k$ with $1 \le k \le n-1$, adding $p_{k-1}$ to both sides of $p_k=(k+1)p_{k-1}+p_{k-2}$ gives

Step 3 (unrolling). Applying Step 2 successively for $k=n-1,n-2,\cdots,1$,

and substituting these in turn (i.e. induction descending from $k=n-1$ to $k=1$) yields

Since $p_{-1}=1$, the last term is $p_0+1$. Substituting into Step 1,

as claimed. Indeed, for $n=3$, $p_0=1, p_1=3, p_2=10, p_3=43$, and

confirming the formula.

By the definition of a simple continued fraction (Definitions 3.1, 3.3), $a_1, \cdots, a_n$ are all positive integers, so $a_k \ge 1$ for $1 \le k \le n$. Also $q_{-1}=0, q_0=1, q_1=a_1 \ge 1$. Applying $a_k \ge 1$ to the recursion $q_k = a_kq_{k-1}+q_{k-2}$ of Theorem 3.8, for $2 \le k \le n$,

By Lemma 3.11, $q_{k-2} \le q_{k-1}$, so $q_{k-1}+q_{k-2} \ge 2q_{k-2}$, and hence

Since $(\ast)$ links $q_k$ to $q_{k-2}$ two steps earlier, we handle even and odd $k$ by induction based on $k=2$ and $k=3$ respectively.

Base case ($k=2$). $q_2 = a_2q_1+q_0 \ge 1\cdot1+1 = 2 \ge \sqrt{2} = 2^{\frac{1}{2}}$, so the claim holds for $k=2$.

Base case ($k=3$). $q_3 = a_3q_2+q_1 \ge q_2+q_1 \ge 2+1 = 3 \ge 2 = 2^1$, so the claim holds for $k=3$.

Inductive step. Let $4 \le k \le n$ and suppose $q_{k-2} \ge 2^{\frac{(k-2)-1}{2}} = 2^{\frac{k-3}{2}}$ already holds (true for $k-2=2,3$ by the base cases, and inductively for every $k-2$ through this same step). Then by $(\ast)$,

so the claim holds for $k$ as well. By mathematical induction (a strong induction proceeding two steps at a time), $q_k \ge 2^{\frac{k-1}{2}}$ for all $2 \le k \le n$.

For $[1; 2, 3, 3, 2, 1]$, $a_0=1, a_1=2, a_2=3, a_3=3, a_4=2, a_5=1$. Applying the recursion $p_k=a_kp_{k-1}+p_{k-2}$, $q_k=a_kq_{k-1}+q_{k-2}$ of Theorem 3.8 (with $p_{-2}=0, q_{-2}=1, p_{-1}=1, q_{-1}=0$),

so the convergents of $[1; 2, 3, 3, 2, 1]$ are, in order,

For $[-3; 1, 1]$, $a_0=-3, a_1=1, a_2=1$, and the same recursion gives

so the convergents of $[-3; 1, 1]$ are, in order,

$3.1416 = \frac{31416}{10000} = \frac{3927}{1250}$. By the (simple continued fraction) algorithm, applying Euclid’s algorithm to $\frac{3927}{1250}$,

Reading off the quotients,

In the same way, applying Euclid’s algorithm to $3.14159 = \frac{314159}{100000}$,

Reading off the quotients,

First we check that no denominator is $0$. Since $a_0 \gt 0$ and $a_1, \cdots, a_n$ are all positive integers, starting from $p_{-1}=1$, $p_0=a_0 \ge 1$ and applying the recursion $p_j=a_jp_{j-1}+p_{j-2}$ of Theorem 3.8 ($p_{-2}=0$), induction gives $p_j \ge 1 \gt 0$ for all $j \ge -1$. Likewise, starting from $q_{-1}=0, q_0=1, q_1=a_1\ge1$, Lemma 3.11 shows $q_j$ is nondecreasing, so $q_j \ge 1 \gt 0$ for all $j \ge 0$. Hence $p_{k-1}$ and $q_{k-1}$ are nonzero for $k \ge 0$ and $k \ge 1$, respectively.

1. Proof of $\frac{p_k}{p_{k-1}} = [a_k; a_{k-1}, \cdots, a_1, a_0]$. We use induction on $k$.

Base case ($k=1$). Since $p_1 = a_1a_0+1$, $p_0=a_0$,

(here $[a_1;a_0]$ is a legitimate continued-fraction symbol since $a_0 \gt 0$ is an integer), which is the desired identity for $k=1$.

Inductive step. Suppose $\frac{p_m}{p_{m-1}} = [a_m; a_{m-1}, \cdots, a_1, a_0]$ holds for some $m$ with $1 \le m \lt n$. By Definition 3.3,

and this equals

(the last equality by the recursion $p_{m+1}=a_{m+1}p_m+p_{m-1}$ of Theorem 3.8). So the identity also holds for $k=m+1$. By induction, $\frac{p_k}{p_{k-1}} = [a_k; a_{k-1}, \cdots, a_1, a_0]$ for all $1 \le k \le n$.

2. Proof of $\frac{q_k}{q_{k-1}} = [a_k; a_{k-1}, \cdots, a_1]$. For $k=1$, since $q_1=a_1$, $q_0=1$,

which is the desired identity for $k=1$ (by the convention that the one-term continued fraction $[a_1]=a_1$). For $2 \le k \le n$ we use the same induction as in 1, taking the identity above at $k=1$ as base case. Suppose $\frac{q_m}{q_{m-1}} = [a_m; a_{m-1}, \cdots, a_1]$ for some $1 \le m \lt n$; by Definition 3.3,

(the last equality by the recursion $q_{m+1}=a_{m+1}q_m+q_{m-1}$ of Theorem 3.8). So the identity also holds for $k=m+1$, and by induction $\frac{q_k}{q_{k-1}} = [a_k; a_{k-1}, \cdots, a_1]$ for all $1 \le k \le n$.

1. Since $\gcd(19,51)=1$, $19x+51y=1$ has integral solutions. Since $\frac{19}{51}=[0;2,1,2,6]$, $a_0=0,a_1=2,a_2=1,a_3=2,a_4=6$, and the recursion of Theorem 3.8 gives

So the convergents are $\frac{0}{1},\frac{1}{2},\frac{1}{3},\frac{3}{8},\frac{19}{51}$, and $n=4$. By Theorem 3.9, $p_nq_{n-1}-q_np_{n-1}=(-1)^{n-1}$, so

Multiplying both sides by $-1$ gives $19\cdot(-8)+51\cdot3=1$, so $(x_0,y_0)=(-8,3)$ is a particular solution of $19x+51y=1$ (check: $19\cdot(-8)+51\cdot3=-152+153=1$). Since $\gcd(19,51)=1$, by Theorems 1.9 and 1.10 the general solution is

2. $\gcd(18,5)=1$. Since $\frac{18}{5}=[3;1,1,2]$, $a_0=3,a_1=1,a_2=1,a_3=2$, and

So the convergents are $\frac{3}{1},\frac{4}{1},\frac{7}{2},\frac{18}{5}$, and $n=3$. By Theorem 3.9,

This already gives a particular solution $(x,y)=(2,-7)$ of $18x+5y=1$ (check: $18\cdot2+5\cdot(-7)=36-35=1$). To reach $18x+5y=24$ we multiply both sides by $24$, so $(x_0,y_0)=(48,-168)$ is a particular solution of $18x+5y=24$ (check: $18\cdot48+5\cdot(-168)=864-840=24$). Since $\gcd(18,5)=1$, by Theorems 1.9 and 1.10 the general solution is

Reparametrizing with $n=n'-9$ gives $x=48+5(n'-9)=3+5n'$, $y=-168-18(n'-9)=-6-18n'$, so this is the same family of solutions written from the simpler particular solution $(x_0,y_0)=(3,-6)$ as $x=3+5n, y=-6-18n$ ($n \in \mathbb{Z}$) (check: $18\cdot3+5\cdot(-6)=54-30=24$).

Theorem 3.12 asserts three things: (1) $C_0 \lt C_2 \lt C_4 \lt \cdots$, (2) $C_1 \gt C_3 \gt C_5 \gt \cdots$, (3) every convergent with an odd script is greater than every convergent with an even script. For $[1;1,1,1,1,1,1,1]$, $a_0=a_1=\cdots=a_7=1$, so the recursion of Theorem 3.8 gives

(the Fibonacci sequence appears exactly). The convergents and their values are

Now we check each item of Theorem 3.12.

(1) Since $C_0=1 \lt C_2=1.5 \lt C_4=1.6 \lt C_6\approx1.6154$, we have $C_0 \lt C_2 \lt C_4 \lt C_6$.

(2) Since $C_1=2 \gt C_3\approx1.6667 \gt C_5=1.625 \gt C_7\approx1.6190$, we have $C_1 \gt C_3 \gt C_5 \gt C_7$.

(3) The maximum of the even-indexed convergents $\{C_0,C_2,C_4,C_6\}$ is $C_6\approx1.6154$, and the minimum of the odd-indexed convergents $\{C_1,C_3,C_5,C_7\}$ is $C_7\approx1.6190$. Since $C_6 \lt C_7$, the maximum even-indexed convergent is less than the minimum odd-indexed convergent, so every even-indexed convergent is less than every odd-indexed convergent. That is, every convergent with an odd script is greater than every convergent with an even script.

All three items are confirmed, so Theorem 3.12 is verified for this continued fraction.