1

I was going through C.Odd's textbook on continued fractions and in the introductory chapter it introduced the formula for the numerator and denominator of the $\ k$ convergent in terms of the numerator and denominator of the $\ k-1$ convergent . If we denote by $\ p_k$ and $\ q_k$ the numerators and denominators of the $\ K $th convergent respectively then :

$\ P_k$ = ($a_k$$\ p_k-1$ +$\ p_k-2$) and $\ q_k$=($\ a_k$$\ q_k-1$ +$\ q_k-2$).............(A)

where $\ a_k$ is the last number in the ladder of the continued fractions . While providing a proof for it by induction the author makes the observation that for the $\ k$+1 th convergent the last number in the ladder of continued fraction is $\ a_k$+1/$\ a_k+1$ instead of $\ a_k$ and hence by replacement of the latter by the former in (A) , would result in an expression which can be molded as the same function of $\ k$+1. However , $\ a_k$ is an integer whereas $\ a_k$+1/$\ a_k+1$ isn't . So , how can we carry on the substitution . The author provided an explanation but I wasn't convinced by it . Can anyone make it clearer ?

Mikhail Tal
  • 29

1 Answers1

1

Here is an example, continued fraction for $\sqrt {29}.$ The top row is the "digits," often written $a_i.$ The next row is the convergents, including the two initial fake convergents, $0/1$ and $1/0,$ that begin the process. You can see how the numerator and denominator of a new convergent are specified by the previous two convergents and the "digit." The final row is $p^2 - 29 q^2$ for convergent $p/q.$

My main recommendation is that you do some of these yourself.

$$ \small \begin{array}{cccccccccccccccccccccccccccccc} & & 5 & & 2 & & 1 & & 1 & & 2 & & 10 & & 2 & & 1 & & 1 & & 2 & & 10 & \\ \frac{0}{1} & \frac{1}{0} & & \frac{5}{1} & & \frac{11}{2} & & \frac{16}{3} & & \frac{27}{5} & & \frac{70}{13} & & \frac{727}{135} & & \frac{1524}{283} & & \frac{2251}{418} & & \frac{3775}{701} & & \frac{9801}{1820} & & \frac{101785}{18901} \\ \\ & 1 & & -4 & & 5 & & -5 & & 4 & & -1 & & 4 & & -5 & & 5 & & -4 & & 1 & & -4 \end{array} $$

All you need to do this is a calculator. Begin with $\sqrt{29} \approx 5.3851.$ Take the fractional part, $0.3851,$ but immediately take the reciprocal of that, $1/0.3851 \approx 2.5962.$ $$ 5.3852, 2.5963, 1.6770, 1.4770, 2.0963, 10.3852, 2.5963, 1.6771, 1.4769, 2.0969, 10.3164... $$ As you can see, even when I tell the calculator to round to four decimal places, we see inaccuracy start to creep in; the number that came out 1.6770 and the 1.6771 are actually equal. More visibly, the 10.3852 and 10.3164 are actually equal.

For the special case of (finite) continued fractions for a rational number, the whole thing can be done with the Euclidean Algorithm, avoiding calculator errors. Indeed, the Extended GCD which takes integers $a,b$ and solves $ax - by = \pm \gcd(a,b)$ is precisely the continued fraction for $a/b,$ which will show $a/b$ in lowest terms $p_n/q_n,$ meanwhile $p_n q_{n-1} - q_n p_{n-1} = (-1)^{n-1},$ this being Theorem 150 in Hardy and Wright. For them, the numbering would be $p_0/q_0 = 5/1$ in the above $\sqrt{29},$ then $p_1/q_1 = 11/2.$ That works, $(-1)^{1-1} = 1$ and $11 \cdot 1 - 2 \cdot 5 = 1.$ Then $(-1)^{2-1} = -1$ and $16 \cdot 2 - 3 \cdot 11 = -1.$ Good, I was worried about odd/even in the numbering.

For the special case of square roots of integers, or any $\frac{A + \sqrt B}{C},$ there is a method, due largely to Gauss and Lagrange, that avoids calculation errors. Here the (infinite) CF's are periodic after one or two initial steps that do not quite repeat..

Will Jagy
  • 139,541