Relationship between degrees of continued fractions

Question

I'm trying to compute the values of differing degrees of continued fractions like $\sqrt 2$, $e$ and other similar fractions. My theory was to take the reduced fraction at an arbitrary depth and the fraction that gets added in the next step and combine them somehow to compute the next deepest fraction.

So for example, $\sqrt 2$ can be expressed first as $\large\frac 1 2$ (the constant $1$ + I figured should be added on at the end) then as $\displaystyle \frac 1 {2 + \frac 1 2}$ which reduces to $\large\frac 2 5$. Then the next step $\displaystyle \frac 1 {2 + \frac 1 {2 + \frac 1 2}}$ which in turn reduces to $\large\frac 5 {12}$.

So in effect, what I'm trying to figure out is how I can go from $\large \frac 1 2$ (knowing the next step is $\large\frac 1 2$) to $\large\frac 2 5$ and then from there again to $\large\frac 5 {12}$ - in a generic way that will work for other continued fractions.

Here's my original attempt ($\frac p q$ is the previously computed fraction, $\frac f g$ is the fraction to add in the next step) which doesn't work at all, but may help you see what I'm trying to do:

$$\frac {p_{n+1}} {q_{n+1}} = \frac {p_n\cdot g_{n+1}+f_{n+1}} {q_n\cdot g_{n+1}+g_{n+1}}$$

Anyways, I'm trying to compute continuous fractions to different depths, preferably inductively, given the previous step and the new fraction to add to the denominator. Any insight you can provide would be wonderful.

Answer 1

If you are looking for a reccurence relation for convergents, for $[a_0;a_1;a_2;\ldots]$ it's $$ \frac{p_{n+1}}{q_{n+1}}=\frac{a_{n+1}p_n+p_{n-1}}{a_{n+1}q_n+q_{n-1}}. $$

P.S. For $\sqrt2=[1;2;2;2;\dots]$ it can be written in even nicer (first-order!) form: $$ \frac{p_{n+1}}{q_{n+1}}=\frac{p_n+2q_n}{p_n+q_n}. $$ Hence (for $\sqrt2$) $$ \begin{pmatrix}p_n\\q_n\end{pmatrix}=\begin{pmatrix}1&2\\1 &1\end{pmatrix}^n\begin{pmatrix}1\\0\end{pmatrix} $$ and it can be computed in $O(\log n)$ time.

(In fact, there is always a formula of this type for periodic continued fraction -- i.e. for quadratic irrationalities. If the period is $T$ it allows to compute $(p_{n+T},q_{n+T})$ knowing only $(p_n,q_n)$. Which, in turn, allows one to compute any convergent in logarithmic time.)

Answer 2

Someone posted an answer here about two hours ago that was correct, but they seem to have deleted it, or SE is glitching and I can't see it. I'll gladly give you the Accepted Answer if you come back and post it again.

If they don't, I was able to find effectively the same answer on Wikipedia, of course. I should have done a little more digging, but if anyone's in the same boat as me, here's the answer, enjoy.

Answer 3

I compute below

$$\displaystyle\begin{pmatrix}p_{n+1 } & p_{n } \\ q_{n+1 } & q_{n}\end{pmatrix}=\begin{pmatrix}2 & 1 \\ 1 & 0\end{pmatrix}^{n+1}.$$

Notation: Instead of $p_{n+1}$ and $q_{n+1}$ let me use respectivelly $A_n$ and $B_n$.

With the initial conditions $A_{-1}=1$, $B_{-1}=0$, $A_{0}=b_{0}$, $B_{0}=1$,

$$\displaystyle\begin{pmatrix}A_{\nu } & A_{\nu -1} \\ B_{\nu } & B_{\nu -1}\end{pmatrix}=\displaystyle\prod_{k=0}^{\nu }\begin{pmatrix}b_{k} & 1 \\ a_{k} & 0\end{pmatrix}\qquad(\text{with }a_0=1)\qquad(\ast)$$

is the matrix notation of the truncated generalized continued fraction

$$\dfrac{A_{n}}{B_{n}}=b_{0}+\underset{\nu =1}{\overset{n}{\mathbf{K}}}\left( \dfrac{a_{\nu}}{b_{\nu}}\right)=b_{0}+\dfrac{a_1}{b_1\ +}\ \dfrac{a_2}{b_2\ +\cdots}\ \ \dfrac{a_n}{b_n} \qquad (0)$$

(the first expression is the Gauss Notation ). Its fundamental second order recurrence relation is given by

$$\left\{ \begin{array}{c}b_{\nu }A_{\nu -1}+a_{\nu }A_{\nu -2}=A_{\nu } \\ b_{\nu }B_{\nu -1}+a_{\nu }B_{\nu -2}=B_{\nu }\end{array}\right. \qquad(\nu=1,2,\dots,n).\qquad (1)$$

For $a_k=1$, we have respectivelly

$$\displaystyle\begin{pmatrix}A_{\nu } & A_{\nu -1} \\ B_{\nu } & B_{\nu -1}\end{pmatrix}=\displaystyle\prod_{k=0}^{\nu }\begin{pmatrix}b_{k} & 1 \\ 1 & 0\end{pmatrix}\qquad(\text{with }a_0=1)\qquad(\ast\ast)$$

and

$$\dfrac{A_{n}}{B_{n}}=b_{0}+\underset{\nu =1}{\overset{n}{\mathbf{K}}}\left( \dfrac{1}{b_{\nu}}\right)\qquad (2)$$

From the equality

$$\sqrt{2}-1=\dfrac{1}{2+\sqrt{2}-1}=\dfrac{1}{2+\dfrac{1}{2+\sqrt{2}-1}}=\cdots $$

we get the following expansion for $\sqrt{2}$

$$\sqrt{2}=1+\underset{\nu =1}{\overset{\infty}{\mathbf{K}}}\left( \dfrac{1}{2}\right) =1+\dfrac{1}{2\ +}\ \dfrac{1}{2\ +}\ \ \dfrac{1}{2\ +\cdots}\qquad (3)$$

whose convergents $A_n$ and $B_n$ are such that

$$\dfrac{A_{n}}{B_{n}}=1+\underset{\nu =1}{\overset{n}{\mathbf{K}}}\left( \dfrac{1}{2}\right)\qquad (4)$$

Since $a_k=1,b_k=2 (k\ge 1)$, the fundamental recurrence for $\sqrt{2}$ is given by the following system

$$\left\{ \begin{array}{c}2A_{\nu -1}+A_{\nu -2}=A_{\nu } \\ 2B_{\nu -1}+B_{\nu -2}=B_{\nu }\end{array}\right. \qquad(\nu=1,2,\dots,n).\qquad (5)$$

or this product of matrices

$$\displaystyle\begin{pmatrix}A_{\nu } & A_{\nu -1} \\ B_{\nu } & B_{\nu -1}\end{pmatrix}=\displaystyle\prod_{k=0}^{\nu }\begin{pmatrix}2 & 1 \\ 1 & 0\end{pmatrix}=\begin{pmatrix}2 & 1 \\ 1 & 0\end{pmatrix}^{\nu}\qquad(\nu=1,2,\dots,n)\qquad(\ast\ast\ast)$$

or in your notation, for $n=0,1,2,\dots$

$$\displaystyle\begin{pmatrix}p_{n+1 } & p_{n } \\ q_{n+1 } & q_{n}\end{pmatrix}=\begin{pmatrix}2 & 1 \\ 1 & 0\end{pmatrix}^{n+1}$$

This is the most compact form I am aware of. Hope this helps!

---

Generalization: For $\sqrt{1+x}$ one can use the algebraic identity

$$\sqrt{1+x}-1=\dfrac{x}{2+\sqrt{1+x}-1}=\dfrac{x}{2+\dfrac{x}{2+\sqrt{1+x}-1}}=\cdots $$

---

References

• Oskar Perron, Die Lehre von den Kettenbrüchen, 3.ª ed., vol. II, B. G. Teubner, Stuttgart, 1957.

• Lisa Lorentzen and Haakon Waadeland, Continued Fractions and Applications, North-Holland, Amsterdam, 1992.

• Sergey Khrushchev , Orthogonal Polynomials and Continued Fractions: From Euler's Point of View, Cambridge University Press, 2008.

Answer 4

An alternative method for generating the convergents of continued fraction, which is essentially a stabilized version of the recurrence in Américo's answer, is due to Lentz, Thompson and Barnett.

Given a continued fraction

$$b_0+\cfrac{a_1}{b_1+\cfrac{a_2}{b_2+\cdots}}$$

the Lentz-Thompson-Barnett scheme relies on the two ratios $C_n=A_n/A_{n-1}$ and $D_n=B_{n-1}/B_n$, where $A_n$ and $B_n$ are the nth numerators and denominators (using the same notation in Américo's answer).

Using the recursions given in Américo's answer, the recursions for $C_n$ and $D_n$ are quickly determined to be

$$C_n=b_n+\frac{a_n}{C_{n-1}},\qquad D_n=\frac1{b_n+a_n D_{n-1}}$$

Letting $Y_n=\frac{A_n}{B_n}$ be the $n$-th convergent, Lentz-Thompson-Barnett runs like so:

$\displaystyle Y_0=b_0,\,C_0=Y_0,\,D_0=0$
$\text{for }n=1,2,\dots$
$$D_n=\frac1{b_n+a_n D_{n-1}}$$ $$C_n=b_n+\frac{a_n}{C_{n-1}}$$ $$H_n=C_n D_n$$ $$Y_n=H_n Y_{n-1}$$ $\text{end for}$

Some modifications are needed in cases where certain denominators become zero, but I'll skip mentioning those since they don't seem to occur for continued fractions of surds.

P.S. Of course, if $b_0=0$, start with $b_1$ instead of $b_0$ and the required fractions become $a_1/Y_n$... ;)