$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 6.2: Main Technical Tool

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

Truncate finite (or infinite) continued fraction $$\alpha=[a_0;a_1,a_2, \ldots, a_n]$$ at the $$k$$-th place (with $$k<n$$ in the finite case). The rational number $$s_k=[a_0;a_1,a_2, \ldots, a_k]$$ is called the $$k$$-th convergent of $$\alpha$$. Define the integers $$p_k$$ and $$q_k$$ by $\label{d2} s_k = \frac{p_k}{q_k}$ written in the reduced form with $$q_k>0$$.

The following recursive transformation law takes place.

[MAIN] For $$k \geq 2$$ $\label{main} \begin{array}{c} \displaystyle p_k=a_kp_{k-1} + p_{k-2} \\ \displaystyle q_k=a_kq_{k-1} + q_{k-2}. \end{array}$

Remark. It does not matter here whether we deal with finite or infinite continued fractions: the convergents are finite anyway. We use the induction argument on $$k$$. For $$k=2$$ the statement is true.

Now, assume ([main]) for $$2 \leq k < l$$. Let $\alpha=[a_0;a_1,a_2,\ldots a_l]=\frac{p_l}{q_l}$ be an arbitrary continued fraction of length $$l+1$$. We denote by $$p_r/q_r$$ the $$r$$-th convergent $$\alpha$$. Consider also the continued fraction $\beta = [a_1;a_2, \ldots, a_l]$ and denote by $$p'_r/q'_r$$ its $$r$$-th convergent. We have $$\alpha=a_0+1/\beta$$ which translates as $\label{l3} \begin{array}{l} p_l=a_0p'_{l-1} + q'_{l-1} \\ q_l=p'_{l-1}. \end{array}$ Also, by the induction assumption, $\label{l4} \begin{array}{l} p'_{l-1}=a_lp'_{l-2} + p'_{l-3} \\ q'_{l-1}=a_lq'_{l-2} + q'_{l-3} \end{array}$ Combining ([l3]) and ([l4]) we obtain the formulas $p_l=a_0(a_lp'_{l-2} + p'_{l-3}) + a_lq'_{l-2} + q'_{l-3} = a_l(a_0p'_{l-2} + q'_{l-2}) + (a_0p'_{l-3} + q'_{l-3}) = a_lp_{l-1} + p_{l-2}$ and $q_l=a_lp'_{l-2} +p'_{l-3}=a_lq_{l-1}+ q_{l-2},$ which complete the induction step. We have thus proved that $s_k = \frac{p_k}{q_k},$ where $$p_k$$ and $$q_k$$ are defined by the recursive formulas ([main]). We still have to check that these are the quantities defined by ([d2]), namely that $$q_k>0$$ and that $$q_k$$ and $$p_k$$ are relatively prime. The former assertion follows from ([main]) since $$a_k>0$$ for $$k>0$$. To prove the latter assertion, multiply the equations ([main]) by $$q_{k-1}$$ and $$p_{k-1}$$ respectively and subtract them. We obtain $\label{l5} p_kq_{k-1} - q_kp_{k-1} = -(p_{k-1}q_{k-2} - q_{k-1} p_{k-2}).$

This concludes the proof of Theorem [main]. As an immediate consequence of ([main]) we find that

$\label{dif1} \frac{p_{k-1}}{q_{k-1}} - \frac{p_k}{q_k} = \frac{(-1)^k}{q_kq_{k-1}}$

and $\frac{p_{k-2}}{q_{k-2}} - \frac{p_k}{q_k} = \frac{(-1)^ka_k}{q_kq_{k-2}}.$ Since all the numbers $$q_k$$ and $$a_k$$ are positive, the above formulas imply the following.

[propord] The subsequence of convergents $$p_k/q_k$$ for even indices $$k$$ is increasing.
The subsequence of convergents $$p_k/q_k$$ for odd indices $$k$$ is decreasing.
Every convergent with an odd index is bigger than every convergent with an even index.

Remark. Proposition [propord] implies that both subsequences of convergents (those with odd indices and those with even indices) have limits. This is a step towards making sense out of an infinite continued fraction: this should be common limit of these two subsequences. It is somehow more technically involved (although still fairly elementary!) to prove that these two limits coincide.

[inequ] Let $$\alpha=[a_0;a_1,a_2,\ldots, a_n]$$. For $$k<n$$ we have $\frac{1}{q_k(q_{k+1}+q_k)} \leq \left\vert \alpha - \frac{p_k}{q_k} \right\vert \leq \frac{1}{q_kq_{k+1}}$

Proof.

Another inequality, which provides the lower bound for the distance between the number $$\alpha$$ and $$k$$-th convergent is slightly more involved. To prove it we first consider the following way to add fractions which students sometimes prefer.

The number $\frac{a+c}{b+d}$ is called the mediant of the two fractions $$a/b$$ and $$c/d$$. (The quantities $$a,b,c$$ and $$d$$ are integers.)

[medi] If $\frac{a}{b} \leq \frac{c}{d}$ then $\frac{a}{b} \leq \frac{a+c}{b+d} \leq \frac{c}{d}.$

Consider now the sequence of fractions $\label{seq} \frac{p_k}{q_k}, \ \frac{p_k+p_{k+1}}{q_k+q_{k+1}}, \ \frac{p_k+2p_{k+1}}{q_k+2q_{k+1}}, \ldots, \frac{p_k+a_kp_{k+1}}{q_k+a_kq_{k+1}}=\frac{p_{k+2}}{q_{k+2}},$ where the last equality follows from ([main]).

It follows that the sequence ([seq]) is increasing if $$k$$ is even and is decreasing if $$k$$ is odd. Thus, in particular, the fraction $\label{l6} \frac{p_k+p_{k+1}}{q_k+q_{k+1}}$ is between the quantities $$p_k/q_k$$ and $$\alpha$$. Therefore the distance between $$p_k/q_k$$ and the fraction ([l6]) is smaller than the distance between $$p_k/q_k$$ and $$\alpha$$: $\left\vert \alpha - \frac{p_k}{q_k} \right\vert \geq \frac{p_k+p_{k+1}}{q_k+q_{k+1}} = \frac{1}{q_k(q_k + q_{k+1})}.$ The second (right) inequality in Theorem [inequ] is now proved. This finishes the proof of Theorem [inequ].
Exercises

1. Check the assertion of Theorem [MAIN] for $$k=2$$.

2. Check that for $$k=2$$ $p_2q_1 - q_2p_1 = -1.$ Hint. Introduce formally $$p_{-1}=1$$ and $$q_{-1}=0$$, check that then formulas [main] are true also for $$k=1$$.

3. Combine the previous exercises with ([l5]) to obtain $q_kp_{k-1}-p_kq_{k-1} = (-1)^k$ for $$k \geq 1$$. Derive from this that $$q_k$$ and $$p_k$$ are relatively prime.

4. Prove Proposition [propord]

5. Combine ([dif1]) with Proposition [propord] to prove the inequality $\left\vert \alpha - \frac{p_k}{q_k} \right\vert \leq \frac{1}{q_kq_{k+1}}.$

6. Prove Lemma [medi]

7. Use ([main]) to show that the sign of the difference between two consecutive fractions in ([seq]) depends only on the parity of $$k$$.

## Contributors

• Dr. Wissam Raji, Ph.D., of the American University in Beirut. His work was selected by the Saylor Foundation’s Open Textbook Challenge for public release under a Creative Commons Attribution (CC BY) license.