Exercise 7.5.5* (Secondary convergents)

Proof.

(a)

By hypothesis, $$\begin{array}{lll}\hfill \mathit{ad}-\mathit{bc}=\pm 1,b>0,d>0,s>0.& & \hfill \end{array}$$

and

$$\frac{a}{b}<\frac{r}{s}<\frac{c}{d},\text{or}\frac{c}{d}<\frac{r}{s}<\frac{a}{b}$$

Suppose that

$$\begin{array}{lll}\hfill \frac{a}{b}<\frac{r}{s}<\frac{c}{d}& & \hfill \text{(1)}\end{array}$$

Note that $\mathit{ad}-\mathit{bc}<0$, thus $\mathit{ad}-\mathit{bc}=-1$ and $\mathit{bc}-\mathit{ad}=1$.

Since $\mathit{bc}-\mathit{ad}=1$,

$$\begin{array}{llll}\hfill \frac{1}{\mathit{bd}}=\frac{c}{d}-\frac{a}{b}& =\left(\frac{c}{d}-\frac{r}{s}\right)+\left(\frac{r}{s}-\frac{a}{b}\right)& \hfill & \\ \hfill & =\frac{\mathit{cs}-\mathit{rd}}{\mathit{ds}}+\frac{\mathit{rb}-\mathit{sa}}{\mathit{sb}}.& \hfill & \end{array}$$

By (1), $\mathit{cs}-\mathit{rd}>0$ and $\mathit{rb}-\mathit{sa}>0$, therefore

$$\frac{1}{\mathit{bd}}\ge \frac{1}{\mathit{ds}}+\frac{1}{\mathit{sb}}=\frac{b+d}{\mathit{bds}},$$

thus $s\ge b+d$. Since $b>0$ and $d>0$, we obtain

$$s>b,s>d.$$

In the case $\frac{c}{d}<\frac{r}{s}<\frac{a}{b}$, exchanging the roles of $a∕b$ and $c∕d$, we prove similarly that $s>b,s>d.$

(Alternatively, we can use the results on Farey sequences, in particular the result of Problem 6.1.5.)

(b)

Consider the finite sequence

$$\begin{array}{lll}\hfill \frac{h_{n-1}}{k_{n-1}},\frac{h_{n-1}+h_n}{k_{n-1}+k_n},\frac{h_{n-1}+2h_n}{k_{n-1}+2k_n},\dots ,\frac{h_{n-1}+a_{n+1}{h}_n}{k_{n-1}+a_{n+1}{k}_n}=\frac{h_{n+1}}{k_{n+1}}.& & \hfill \text{(2)}\end{array}$$

Let, for $0\le j<a_{n+1}$,

$$\begin{array}{llll}\hfill \frac{a}{b}& =\frac{h_{n-1}+j{h}_n}{k_{n-1}+j{k}_n},& \hfill & \end{array}$$

and

$$\begin{array}{llll}\hfill \frac{c}{d}& =\frac{h_{n-1}+(j+1)h_n}{k_{n-1}+(j+1)k_n},& \hfill & \end{array}$$

be two consecutive terms in the sequence (2). Then

$$\begin{array}{llll}\hfill \mathit{ad}-\mathit{bc}& =(h_{n-1}+j{h}_n)(k_{n-1}+(j+1)k_n)-(k_{n-1}+j{k}_n)(h_{n-1}+(j+1)h_n)& \hfill & \\ \hfill & =(h_{n-1}+j{h}_n)k_n-(k_{n-1}+j{k}_n)h_n& \hfill & \\ \hfill & =h_{n-1}{k}_n-k_{n-1}{h}_n& \hfill & \\ \hfill & ={(-1)}^n& \hfill & \end{array}$$

by Theorem 7.5. Therefore

$$\begin{array}{llll}\hfill \frac{c}{d}-\frac{a}{b}& =\frac{{(-1)}^{n+1}}{(k_{n-1}+j{k}_n)(k_{n-1}+(j+1)k_n)},& \hfill & \end{array}$$

Since the denominator is positive, the sign of $c∕d-a∕b$ doesn’t depend of $j$, and is positive if $n$ is odd, negative if $n$ is even.

This shows that the sequence (2) is strictly increasing if $n$ is odd, strictly decreasing if $n$ is even.

(c)

(I used Khinchin “Continued Fractions”, p. 22,23 to write the solution of this question.)

Important note : In the definition of secondary convergent, we must consider also the value $n=0$ (this is not clear in the statement, which says “here $n$ runs through all values $1,2,\dots$”). Since $k_{-1}=0$, $h_{-1}∕k_{-1}$ is not defined, but all other fractions in the sequence of (b) for $n=0$ are defined and some of them may be fair approximations: they are

$$\begin{array}{lll}\hfill & \frac{h_{-1}+h_0}{k_{-1}+k_0}>\frac{h_{-1}+2h_0}{k_{-1}+2k_0}>\cdots >\frac{h_{-1}+a_1{h}_0}{k_{-1}+a_1{k}_0}=\frac{h_1}{k_1},& \hfill \text{(3)}\end{array}$$

explicitly

$$\begin{array}{lll}\hfill & a_0+1>a_0+\frac{1}{2}>\cdots >a_0+\frac{1}{a_1}=\frac{h_1}{k_1}.& \hfill \text{(4)}\end{array}$$

For instance, consider $\sqrt{10}=⟨3,6,6,6,6,\dots ,⟩$. Then the secondary convergents given by (3) or (4) are

$$4>\frac{7}{2}>\frac{10}{3}>\frac{13}{4}>\frac{16}{5}\left(>\frac{19}{6}=\frac{h_1}{k_1}\right).$$

Then $19∕6$ is a convergent, and $13∕4$ and $16∕5$ are fair approximations (but not $4,\frac{7}{2},\frac{10}{3}$ (see part (d) for the verifications). So it is essential to consider these fractions as secondary convergents. (End of the note.)

Consider a good approximation $a∕b$ of $\xi$, so that

$$\begin{array}{lll}\hfill |\mathit{\xi b}-a|=\underset{(x,y)\in {\mathbb{Z}}^2,0<y\le k_n}{\min <!--\; FUNCTION\; APPLICATION\; -->}|\mathit{\xi y}-x|.& & \hfill \end{array}$$

Therefore

$$\begin{array}{lll}\hfill \forall <!--\; FUNCTION\; APPLICATION\; -->x\in \mathbb{Z},\forall <!--\; FUNCTION\; APPLICATION\; -->y\in ]]0,b]],|\mathit{\xi b}-a|\le |\mathit{\xi y}-x|.& & \hfill \text{(5)}\end{array}$$

For all $y$ such that $0<y\le b$, we have $0<1∕b\le 1∕y$ and $|\mathit{\xi b}-a|\le |\mathit{\xi y}-x|$. Multiplying these two inequalities, we obtain

$$\begin{array}{lll}\hfill \forall <!--\; FUNCTION\; APPLICATION\; -->x\in \mathbb{Z},\forall <!--\; FUNCTION\; APPLICATION\; -->y\in ]]0,b]],\left|\xi -\frac{a}{b}\right|\le \left|\xi -\frac{x}{y}\right|.& & \hfill \end{array}$$

Hence

$$\left|\xi -\frac{a}{b}\right|=\underset{(x,y)\in {\mathbb{Z}}^2,0<y\le b}{\min <!--\; FUNCTION\; APPLICATION\; -->}\left|\xi -\frac{x}{y}\right|,$$

so $a∕b$ is a fair approximation to $\xi$. Every good approximation is a fair approximation.

Conversely, consider a fair approximation $a∕b$ to $\xi$, so that

$$\begin{array}{lll}\hfill \forall <!--\; FUNCTION\; APPLICATION\; -->x\in \mathbb{Z},\forall <!--\; FUNCTION\; APPLICATION\; -->y\in ]]0,b]],\left|\xi -\frac{a}{b}\right|\le \left|\xi -\frac{x}{y}\right|.& & \hfill \text{(6)}\end{array}$$

We note first that $a∕b\ge a_0$, otherwise $a∕b<a_0<\xi$, so $\left|\xi -\frac{a_0}{1}\right|<\left|\xi -\frac{a}{b}\right|$, where $b\ge 1$: this contradicts (6). Therefore $\frac{a}{b}\ge a_0=r_0$ (we recall that $r_n=h_n∕k_n$).

Moreover $a∕b\le a_0+1$, otherwise $\xi <a_0+1<a∕b$, so $\left|\xi -\frac{a_0+1}{1}\right|<\left|\xi -\frac{a}{b}\right|$, where $b\ge 1$: this contradicts (6). So

$$a_0\le \frac{a}{b}\le a_0+1.$$

For clarity, we expose separately the cases $a∕b<\xi$ and $a∕b>\xi$ (since $\xi$ is an irrational number, the equality $\xi =a∕b$ is impossible).

$\text{∙}$ Suppose that $a∕b<\xi$. Since the sequence ${(r_{2l})}_{l\in \mathbb{N}}$ is strictly increasing, with limit $\xi$,

$$[a_0,\xi [=\underset{l\in \mathbb{N}}{\bigcup }[r_{2l},r_{2l+2}[=\underset{k\in \mathbb{N}}{\bigcup }\left[\frac{h_{2l}}{k_{2l}},\frac{h_{2l+2}}{k_{2l+2}}\right[.$$

Since $a∕b\in [a_0,\xi [$, there is some odd integer $n=2l+1$ such that

$$\frac{a}{b}\in \left[\frac{h_{n-1}}{k_{n-1}},\frac{h_{n+1}}{k_{n+1}}\right[.$$

By part (b), since the finite sequence ${\left(\frac{h_{n-1}+j{h}_n}{k_{n-1}+j{k}_n}\right)}_{0\le j\le a_{n+1}}$ is strictly increasing,

$$\left[\frac{h_{n-1}}{k_{n-1}},\frac{h_{n+1}}{k_{n+1}}\right[=\underset{0\le j\le a_{n+1}-1}{\bigcup }\left[\frac{h_{n-1}+j{h}_n}{k_{n-1}+j{k}_n},\frac{h_{n-1}+(j+1)h_n}{k_{n-1}+(j+1)k_n}\right[.$$

Therefore there exists an odd integer $n\ge 1$ and an integer $j$ ( $0\le j<a_{n+1}$) such that

$$\begin{array}{lll}\hfill \frac{h_{n-1}+j{h}_n}{k_{n-1}+j{k}_n}\le \frac{a}{b}<\frac{h_{n-1}+(j+1)h_n}{k_{n-1}+(j+1)k_n}.& & \hfill \text{(7)}\end{array}$$

Assume, for the sake of contradiction, that $\frac{h_{n-1}+j{h}_n}{k_{n-1}+j{k}_n}\ne \frac{a}{b}$. Then

$$\begin{array}{lll}\hfill 0<\frac{a}{b}-\frac{h_{n-1}+j{h}_n}{k_{n-1}+j{k}_n}& <\frac{h_{n-1}+(j+1)h_n}{k_{n-1}+(j+1)k_n}-\frac{h_{n-1}+j{h}_n}{k_{n-1}+j{k}_n}.& \hfill \text{(8)}\end{array}$$

Using part (b), this gives

$$\begin{array}{lll}\hfill 0<\frac{a}{b}-\frac{h_{n-1}+j{h}_n}{k_{n-1}+j{k}_n}& <\frac{1}{(k_{n-1}+j{k}_n)(k_{n-1}+(j+1)k_n)}& \hfill \text{(9)}\end{array}$$

Moreover, there is an integer $m$ such that

$$0<\frac{a}{b}-\frac{h_{n-1}+j{h}_n}{k_{n-1}+j{k}_n}=\frac{m}{b(k_{n-1}+j{k}_n)}.$$

Therefore $m>0$, so $m\ge 1$, hence

$$\frac{1}{b(k_{n-1}+j{k}_n)}\le \frac{a}{b}-\frac{h_{n-1}+j{h}_n}{k_{n-1}+j{k}_n}<\frac{1}{(k_{n-1}+j{k}_n)(k_{n-1}+(j+1)k_n)}.$$

This shows that

$$b>k_{n-1}+(j+1)k_n.$$

By (5) and part (b),

$$\begin{array}{lll}\hfill \frac{h_{n-1}+j{h}_n}{k_{n-1}+j{k}_n}\le \frac{a}{b}<\frac{h_{n-1}+(j+1)h_n}{k_{n-1}+(j+1)k_n}<\frac{h_{n+1}}{k_{n+1}}<\xi .& & \hfill \text{(10)}\end{array}$$

Therefore

$$\left|\xi -\frac{h_{n-1}+(j+1)h_n}{k_{n-1}+(j+1)k_n}\right|<\left|\xi -\frac{a}{b}\right|,$$

where $b>k_{n-1}+(j+1)k_n.$ This contradicts (6) and the hypothesis that $a∕b$ is a fair approximation to $\xi$.

We have proved that

$$\frac{a}{b}=\frac{h_{n-1}+j{h}_n}{k_{n-1}+j{k}_n}(n\ge 1,0\le j<a_k),$$

so $a∕b$ is a convergent or a secondary convergent to $\xi$.

$\text{∙}$ Suppose that $a∕b>\xi$. Since the sequence ${(r_{2l+1})}_{l\in \mathbb{N}}$ is strictly decreasing, with limit $\xi$,

$$]\xi ,a_0+1]=\left(\underset{l\in \mathbb{N}}{\bigcup }]r_{2l+3},r_{2l+1}]\right)\cup ]r_1,a_0+1].$$

Since $a∕b\in ]\xi ,a_0+1]$, there is some even integer $n=2l+2$ such that

$$\frac{a}{b}\in \left]\frac{h_{n+1}}{k_{n+1}},\frac{h_{n-1}}{k_{n-1}}\right]\text{ or }\frac{a}{b}\in ]r_1,a_0+1].$$

By part (b), since the finite sequence ${\left(\frac{h_{n-1}+j{h}_n}{k_{n-1}+j{k}_n}\right)}_{1\le j\le a_{n+1}}$ is strictly decreasing,

$$\left]\frac{h_{n+1}}{k_{n+1}},\frac{h_{n-1}}{k_{n-1}}\right]=\underset{0\le j\le a_k-1}{\bigcup }\left]\frac{h_{n-1}+(j+1)h_n}{k_{n-1}+(j+1)k_n},\frac{h_{n-1}+j{h}_n}{k_{n-1}+j{k}_n}\right],$$

and by (3),

$$]r_1,a_0+1]=\left]\frac{h_1}{k_1},\frac{h_{-1}+h_0}{k_{-1}+k_0}\right]=\underset{1\le j\le a_1-1}{\bigcup }\left]\frac{h_{-1}+(j+1)h_0}{k_{-1}+(j+1)k_0},\frac{h_{-1}+j{h}_0}{k_{n-1}+j{k}_n}\right].$$

Therefore there exists an even integer $n\ge 0$ and an integer $j$ ( $0\le j<a_{n+1}$ if $n>0$, $1\le j<a_1$ if $n=0$) such that

$$\begin{array}{lll}\hfill \frac{h_{n-1}+(j+1)h_n}{k_{n-1}+(j+1)k_n}<\frac{a}{b}\le \frac{h_{n-1}+j{h}_n}{k_{n-1}+j{k}_n}.& & \hfill \text{(11)}\end{array}$$

Assume, for the sake of contradiction, that $\frac{h_{n-1}+j{h}_n}{k_{n-1}+j{k}_n}\ne \frac{a}{b}$. Then

$$\begin{array}{lll}\hfill 0<\left|\frac{a}{b}-\frac{h_{n-1}+j{h}_n}{k_{n-1}+j{k}_n}\right|& <\left|\frac{h_{n-1}+(j+1)h_n}{k_{n-1}+(j+1)k_n}-\frac{h_{n-1}+j{h}_n}{k_{n-1}+j{k}_n}\right|.& \hfill \text{(12)}\end{array}$$

Using part (b), this gives

$$\begin{array}{lll}\hfill 0<\left|\frac{a}{b}-\frac{h_{n-1}+j{h}_n}{k_{n-1}+j{k}_n}\right|& <\frac{1}{(k_{n-1}+j{k}_n)(k_{n-1}+(j+1)k_n)}& \hfill \text{(13)}\end{array}$$

Moreover, there is an integer $m$ such that

$$0<\left|\frac{a}{b}-\frac{h_{n-1}+j{h}_n}{k_{n-1}+j{k}_n}\right|=\frac{m}{b(k_{n-1}+j{k}_n)}.$$

Therefore $m>0$, so $m\ge 1$, hence

$$\frac{1}{b(k_{n-1}+j{k}_n)}\le \left|\frac{a}{b}-\frac{h_{n-1}+j{h}_n}{k_{n-1}+j{k}_n}\right|<\frac{1}{(k_{n-1}+j{k}_n)(k_{n-1}+(j+1)k_n)}.$$

This shows that

$$b>k_{n-1}+(j+1)k_n.$$

By (11) and part (b),

$$\begin{array}{lll}\hfill \xi <\frac{h_{n+1}}{k_{n+1}}\le \frac{h_{n-1}+(j+1)h_n}{k_{n-1}+(j+1)k_n}<\frac{a}{b}\le \frac{h_{n-1}+j{h}_n}{k_{n-1}+j{k}_n}.& & \hfill \text{(14)}\\ \hfill & & \hfill \text{(15)}\end{array}$$

Therefore

$$\left|\xi -\frac{h_{n-1}+(j+1)h_n}{k_{n-1}+(j+1)k_n}\right|<\left|\xi -\frac{a}{b}\right|,$$

where $b>k_{n-1}+(j+1)k_n.$ This contradicts (4) and the hypothesis that $a∕b$ is a fair approximation to $\xi$.

We have proved that

$$\frac{a}{b}=\frac{h_{n-1}+j{h}_n}{k_{n-1}+j{k}_n},$$

so $a∕b$ is a convergent or a secondary convergent to $\xi$ (in the sense given in the note).

Every fair approximation is either a convergent or a secondary convergent to $\xi$.

(d)

If $\xi =\sqrt{2}$, $h_0=a_0=\lfloor \xi \rfloor =1$, $2=\frac{a_0+1}{1}=\frac{h_{-1}+h_0}{k_{-1}+k_0}$ is a secondary convergent (see the note in part (c)).

But $\frac{a_0+1}{1}=2$ is not a fair approximation, because $\left|\sqrt{2}-\frac{1}{1}\right|<\left|\sqrt{2}-\frac{2}{1}\right|$.

(It seems experimentally that all other secondary convergent are fair approximations to $\sqrt{2}$: to be verified.)

A more interesting example is $\sqrt{10}$ (see the note of part (c)). Then among the secondary convergents

$$4>\frac{7}{2}>\frac{10}{3}>\frac{13}{4}>\frac{16}{5}\left(>\frac{19}{6}=\frac{h_1}{k_1}\right),$$

only $13∕4$ and $16∕5$ are fair approximations.

With Sagemath,

     def is_fair_approximation(xi, f):
         a0 = int(xi)
         a, b = f.numer(), f.denom()
         test = true
         for y in range(1, b+1):
             for x in range(a0 * y, a0 * y + y + 1):
                 if abs(xi - f) > abs(xi -x/y):
                     test = false
         return test
     
     cvg = continued_fraction(sqrt(10)); cvg
              [3; 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, ...]
     
     l = [cvg.convergent(i) for i in range(6)]; l
              [3, 19/6, 117/37, 721/228, 4443/1405, 27379/8658]
     
     secondary = [3 + 1/i for i in range(1,7)]; secondary
     
     for f in secondary:
         print(f, is_fair_approximation(sqrt(10), f))
     
             
         (4, False)
         (7/2, False)
         (10/3, False)
         (13/4, True)
         (16/5, True)
         (19/6, True)

(e)

The set of fair approximations of $\xi \in ℝ\setminus \mathbb{Q}$ is an infinite set, since every convergent $h_n∕k_n$ with $n\ge 1$ is a good approximation by Problem 3, and every good approximation is a fair approximation by part (c).

If $a∕b$ and $c∕d$ are two distinct fair approximations to $\xi$, then $|\xi -a∕b|\ne |\xi -c∕d|$. Indeed, if $|\xi -a∕b|=|\xi -c∕d|$, then $\xi -a∕b=𝜀(\xi -c∕d)$ where $𝜀=\pm 1$. If $𝜀=-1$, then $\xi =(1∕2)(a∕b+c∕d)$: this is impossible because $\xi$ is irrational. Thus $𝜀=1$, so $a∕b=c∕d$.

This allows us to order the set of fair approximations to $\xi$ in a sequence $r_1,r_2,r_3,\dots$ so that

$$\begin{array}{lll}\hfill |\xi -r_{j+1}|<|\xi -r_j|,j\in {\mathbb{N}}^{\text{∗}}.& & \hfill \text{(16)}\end{array}$$

Since $r_j$ is a fair approximation to $\xi$, the inequality (16) implies that $r_{j+1}>r_j$, so the sequence ${(|\xi -r_j|)}_{j\in {\mathbb{N}}^{\text{∗}}}$ is strictly decreasing.

It remains to show that $\underset{j\to \infty }{\lim <!--\; FUNCTION\; APPLICATION\; -->}{r}_j=\xi$.

Let $𝜀$ be any positive real number. Since $\underset{n\to \infty }{\lim <!--\; FUNCTION\; APPLICATION\; -->}{h}_n∕k_n=\xi$, there is some positive integer $N$ such that $|\xi -h_N∕k_N|<𝜀$. By the first remark of part (a), $h_N∕k_N$ is a fair approximation, so there is some positive integer $J$ such that $r_J=h_N∕k_N$, so $|\xi -r_J|<𝜀|$. Since ${(|\xi -r_j|)}_{j\in \mathbb{N}}$ is a strictly decreasing sequence by (16), for all $j\in \mathbb{N}$, $j\ge J\Rightarrow |\xi -r_j|<|\xi -r_J|<𝜀$. In conclusion,

$$\forall <!--\; FUNCTION\; APPLICATION\; -->𝜀>0,\exists <!--\; FUNCTION\; APPLICATION\; -->J\in \mathbb{N},\forall <!--\; FUNCTION\; APPLICATION\; -->j\in \mathbb{N},j\ge J\Rightarrow |\xi -r_j|<𝜀.$$

This shows that

$$\underset{j\to \infty }{\lim <!--\; FUNCTION\; APPLICATION\; -->}{r}_j=\xi .$$

Therefore ${(r_j)}_{j\in {\mathbb{N}}^{\text{∗}}}$ is an approximating sequence.

(f)

Note: We must take as first element of the sequence $h_0∕k_0=a_0$, otherwise the insertion of this element at the beginning gives also an approximating sequence.

We consider the sequence obtained by first taking $r_0=h_0∕k_0$, then the terms of $S_1$:

$$r_1=\frac{h_0+h_1}{k_0+k_1}<\frac{h_0+2h_1}{k_0+2k_1}<\dots <\frac{h_0+a_2{h}_1}{k_0+a_2{k}_1}=\frac{h_2}{k_2},$$

then the terms of $S_2$,

$$\frac{h_2+h_3}{k_2+k_3}<\frac{h_2+2h_3}{k_2+2k_3}<\dots <\frac{h_2+a_4{h}_3}{k_2+a_4{k}_3}=\frac{h_4}{k_4},$$

and so on.

By part (b), this gives a strictly increasing sequence of terms, all strictly less than $\xi$. Therefore for all $j\ge 0$,

$$|\xi -r_{j+1}|=\xi -r_{j+1}<\xi -r_j=|\xi -r_j|.$$

Moreover, since

$$k_0<k_0+k_1<\cdots <k_0+a_2{k}_1=k_2<k_2+k_3<k_2+a_4{k}_2=k_4<\cdots ,$$

the sequence of denominators of the $r_j$ is strictly increasing.

Since the sequence ${(r_j)}_{j\in \mathbb{N}}$ is increasing, and $r_j<\xi$ for all $j$, this sequence is convergent (to $l\le \xi$). Moreover the subsequence $(h_n∕k_n)$ has limit $\xi$. Since every subsequence has limit $l$, we obtain $l=\xi$, so

$$\underset{j\to \infty }{\lim <!--\; FUNCTION\; APPLICATION\; -->}{r}_j=\xi .$$

The sequence ${(r_j)}_{j\in \mathbb{N}}$ is an approximating sequence.

We prove that this sequence is maximal. Suppose that we introduce some rational $\alpha =p∕q(q>0)$ in this sequence, where $\alpha <\xi$ and $\alpha \ne r_j$ for all $j$. Assume, for the sake of contradiction, that this new sequence is also an approximating sequence.

Since $r_0=a_0∕1$ and since the sequence of denominators is strictly increasing, $p∕q<a_0$ is impossible (otherwise $0<q<1$), thus $a_0=h_0∕k_0<\alpha <\xi$. Therefore, there is some integer $n\ge 0$ and some integer $j$ ( $0\le j<a_{n+2})$ such that

$$\begin{array}{lll}\hfill \frac{h_n+j{h}_{n+1}}{k_n+j{k}_{n+1}}<\frac{p}{q}<\frac{h_n+(j+1)h_{n+1}}{k_n+(j+1)k_{n+1}},k_n+j{k}_{n+1}<q<k_n+(j+1)k_{n+1}.& & \hfill \text{(17)}\end{array}$$

Then

$$\begin{array}{llll}\hfill 0<\frac{p}{q}-\frac{h_n+j{h}_{n+1}}{k_n+j{k}_{n+1}}& <\frac{h_n+(j+1)h_{n+1}}{k_n+(j+1)k_{n+1}}-\frac{h_n+j{h}_{n+1}}{k_n+j{k}_{n+1}},& \hfill & \end{array}$$

thus by part (b),

$$\begin{array}{lll}\hfill 0<\frac{p}{q}-\frac{h_n+j{h}_{n+1}}{k_n+j{k}_{n+1}}& \le \frac{1}{(k_n+j{k}_{n+1})(k_n+(j+1)k_{n+1})}.& \hfill \text{(18)}\end{array}$$

Moreover

$$\begin{array}{lll}\hfill \frac{p}{q}-\frac{h_n+j{h}_{n+1}}{k_n+j{k}_{n+1}}=\frac{m}{q(k_n+j{k}_{n+1})},& & \hfill \end{array}$$

where $m$ is an integer, and $m>0$, so $m\ge 1$. This gives

$$\begin{array}{lll}\hfill \frac{p}{q}-\frac{h_n+j{h}_{n+1}}{k_n+j{k}_{n+1}}\ge \frac{1}{q(k_n+j{k}_{n+1})}.& & \hfill \text{(19)}\end{array}$$

Taking together (18) and (19), we obtain

$$\begin{array}{lll}\hfill \frac{1}{q(k_n+j{k}_{n+1})}& \le \frac{1}{(k_n+j{k}_{n+1})(k_n+(j+1)k_{n+1})},& \hfill \text{(20)}\end{array}$$

thus $q\ge k_n+(j+1)k_{n+1})$, which contradicts (17).

This contradiction shows that ${(r_j)}_{j\in \mathbb{N}}$ is a maximal approximation sequence.

(g)

For this question, there is no element to insert before $S_{-1}$, because $k_{-1}=0$, $h_{-1}∕k_{-1}$ is not defined. We consider the sequence obtained by first taking the terms of $S_{-1}$ in order $$r_1=a_0+1=\frac{h_{-1}+h_0}{k_{-1}+k_0}>\frac{h_{-1}+2h_0}{k_{-1}+2k_0}>\dots >\frac{h_{-1}+a_1{h}_0}{k_0+a_1{k}_0}=\frac{h_1}{k_1},$$

then the terms of $S_1$:

$$\frac{h_1+h_2}{k_1+k_2}>\frac{h_1+2h_2}{k_1+2k_2}>\dots >\frac{h_1+a_3{h}_2}{k_1+a_3{k}_2}=\frac{h_3}{k_3},$$

and so on.

This gives a strictly decreasing sequence of terms, all strictly greater than $\xi$. We prove as in part (f) that the sequence ${(r_j)}_{j\in {\mathbb{N}}^{\text{∗}}}$ is an approximating sequence.

Suppose that we introduce some rational $\alpha =p∕q(q>0)$ in this sequence, where $\alpha >\xi$ and $\alpha \ne r_j$ for all $j$. Assume, for the sake of contradiction, that this new sequence is also an approximating sequence.

Since $r_1=(a_0+1)∕1$ and since the sequence of denominators is strictly increasing, $p∕q>a_0+1$ is impossible (otherwise $0<q<1$), thus $\xi <\alpha <a_0+1$. Therefore, there is some integer $n\ge 0$ and some integer $j$ ( $0\le j<a_{n+2})$ such that

$$\begin{array}{lll}\hfill \frac{h_n+j{h}_{n+1}}{k_n+j{k}_{n+1}}>\frac{p}{q}>\frac{h_n+(j+1)h_{n+1}}{k_n+(j+1)k_{n+1}},k_n+j{k}_{n+1}<q<k_n+(j+1)k_{n+1}.& & \hfill \text{(21)}\end{array}$$

The remainder of the proof is similar, so ${(r_j)}_{j\in {\mathbb{N}}^{\text{∗}}}$ is a maximal approximating sequence.