6.2: Main Technical Tool
 Page ID
 8853
\( \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_{k1} + p_{k2} \\ \displaystyle q_k=a_kq_{k1} + q_{k2}. \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'_{l1} + q'_{l1} \\ q_l=p'_{l1}. \end{array}\] Also, by the induction assumption, \[\label{l4} \begin{array}{l} p'_{l1}=a_lp'_{l2} + p'_{l3} \\ q'_{l1}=a_lq'_{l2} + q'_{l3} \end{array}\] Combining ([l3]) and ([l4]) we obtain the formulas \[p_l=a_0(a_lp'_{l2} + p'_{l3}) + a_lq'_{l2} + q'_{l3} = a_l(a_0p'_{l2} + q'_{l2}) + (a_0p'_{l3} + q'_{l3}) = a_lp_{l1} + p_{l2}\] and \[q_l=a_lp'_{l2} +p'_{l3}=a_lq_{l1}+ q_{l2},\] 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_{k1}\) and \(p_{k1}\) respectively and subtract them. We obtain \[\label{l5} p_kq_{k1}  q_kp_{k1} = (p_{k1}q_{k2}  q_{k1} p_{k2}).\]
This concludes the proof of Theorem [main]. As an immediate consequence of ([main]) we find that
\[\label{dif1} \frac{p_{k1}}{q_{k1}}  \frac{p_k}{q_k} = \frac{(1)^k}{q_kq_{k1}}\]
and \[\frac{p_{k2}}{q_{k2}}  \frac{p_k}{q_k} = \frac{(1)^ka_k}{q_kq_{k2}}.\] 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

Check the assertion of Theorem [MAIN] for \(k=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\).

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

Prove Proposition [propord]

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}}.\]

Prove Lemma [medi]

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.