Skip to main content
\(\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}}\)
Mathematics LibreTexts

6.2: Main Technical Tool

[ "article:topic", "authorname:wraji", "showtoc:no" ]
  • 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_{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.