Predicting the change in the denominator of a continued fraction when reversing the order of $a_1$ through $a_n$.

192 Views Asked by At

When reversing the order of $a_1$ through $a_n$ in a continued/extended fraction, (ie. [$a_1$: $a_2$, ... $a_{n-1}$, $a_n$] becomes [$a_n$: $a_{n-1}$, ... $a_2$, $a_1$]) we see that the denominator changes, but the numerator remains the same.

$a_1+\frac{1}{a_2+\frac{1}{...+\frac{1}{a_n}}}\\$ = $\frac{A}{B}$ $\Rightarrow$ $a_n+\frac{1}{...+\frac{1}{a_2+\frac{1}{a_1}}}\\$ = $\frac{A}{C}$

For example:

$2+\frac{1}{3+\frac{1}{4+\frac{1}{5}}}$ = $\frac{157}{68}$

and

$5+\frac{1}{4+\frac{1}{3+\frac{1}{2}}}$ = $\frac{157}{30}$

Is there a way to predict exactly how the denominator will change without simplifying to an improper fraction?

1

There are 1 best solutions below

0
On BEST ANSWER

Most definitely. Steps:

  1. The following link proves the connection between the elements of a continued fraction and the elements produced by the euclidean algorithm: Show that the elimination of the successive remainders from the Euclidean algorithm leads to a finite expansion.

  2. Examine the following link, which establishes a common notation and (in its Example section) shows an easy way to calculate $p_1, p_2, ..., q_1, q_2, ...$ : https://crypto.stanford.edu/pbc/notes/contfrac/definition.html.

  3. Assume that $a_1, a_2, \cdots a_k$ are known and that $p_k,q_k$ are known. The following analysis proves that $[a_k; a_{k-1}, \cdots, a_1] = \frac{p_k}{p_{k-1}}.$ The problem therefore reduces to using the method in step 2 above to calculate $p_{k-1}.$

For $k=2, \frac{p_2}{p_1} = \frac{a_2 a_1 + 1}{a_1} = a_2 + \frac{1}{a_1} = [a_2;a_1].$

For $k>2,\;$ inductively assume that $\;[a_{k-1}; a_{k-2}, \cdots, a_1] = \frac{p_{k-1}}{p_{k-2}}.$

Thus, $\;p_k = a_k p_{k-1} + p_{k-2} \;\Rightarrow$
$\frac{p_k}{p_{k-1}} = a_k + \frac{p_{k-2}}{p_{k-1}} = a_k + \frac{1}{\frac{p_{k-1}}{p_{k-2}}} = [a_k; a_{k-1}, a_{k-2}, \cdots, a_1].$