6.2: Main Technical Tool

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 and Attributions

• 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.