1
$\begingroup$

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 ?

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.