Convergence of Infinite Continued Fractions

Lemma 5.2   For every $n$ such that $a_n$ is defined, we have

$$x = [a_0, a_1, \ldots, a_{n}+t_n],$$

and if $t_{n}\neq 0$ then $x = [a_0, a_1, \ldots, a_{n}, \frac{1}{t_n}].$

Proof. We use induction. The statements are both true when $n=0$ . If the second statement is true for $n-1$ , then

$$x = \left[a_0,a_1, \ldots, a_{n-1},\frac{1}{t_{n-1}}\right]$$

$$=\left[a_0,a_1, \ldots, a_{n-1},a_n + t_n\right]$$

$$=\left[a_0,a_1, \ldots, a_{n-1},a_n, \frac{1}{t_n}\right].$$

Similarly, the first statement is true for $n$ if it is true for $n-1$ . $\qedsymbol$

Theorem 5.2 (Continued Fraction Limit)   Let $a_0,a_1,\ldots$ be a sequence of integers such that $a_n>0$ for all $n\geq 1$ , and for each $n\geq 0$ , set $c_n = [a_0, a_1, \ldots a_n].$ Then $$\lim_{n\rightarrow \infty} c_n$$ exists.

Proof. For any $m\geq n$ , the number $c_n$ is a partial convergent of $[a_0,\ldots,a_m]$ . By Proposition 5.1.13 the even convergents $c_{2n}$ form a strictly increasing sequence and the odd convergents $c_{2n+1}$ form a strictly decreasing sequence. Moreover, the even convergents are all $\leq c_1$ and the odd convergents are all $\geq c_0$ . Hence $\alpha_0 = \lim_{n\rightarrow \infty} c_{2n}$ and $\alpha_1 = \lim_{n\rightarrow \infty} c_{2n+1}$ both exist and $\alpha_0\leq \alpha_1$ . Finally, by Proposition 5.1.7

$$\vert c_{2n} - c_{2n-1}\vert = \frac{1}{q_{2n}\cdot q_{2n-1}} \leq \frac{1}{2n(2n-1)} \rightarrow 0,$$

so $\alpha_0 = \alpha_1$ . $\qedsymbol$

We define

$$[a_0, a_1, \ldots ] = \lim_{n\rightarrow \infty} c_n.$$

Example 5.2   We illustrate the theorem with $x=\pi$ . As in the proof of Theorem 5.2.6, let $c_n$ be the $n$ th partial convergent to $\pi$ . The $c_n$ with $n$ odd converge down to $\pi$

$$c_1 = 3.1428571\ldots, c_3 = 3.1415929\ldots, c_5=3.1415926\ldots$$

whereas the $c_n$ with $n$ even converge up to $\pi$

$$c_2 = 3.1415094\ldots, c_4 = 3.1415926\ldots, c_6=3.1415926\ldots.$$

Theorem 5.2   Let $a_0, a_1, a_2, \ldots$ be a sequence of real numbers such that $a_n>0$ for all $n\geq 1$ , and for each $n\geq 0$ , set $c_n = [a_0, a_1, \ldots a_n].$ Then $$\lim_{n\rightarrow \infty} c_n$$ exists if and only if the sum $\sum_{n=0}^{\infty} a_n$ diverges.

Proof. We only prove that if $\sum a_n$ diverges then $\lim_{n\rightarrow \infty} c_n$ exists. A proof of the converse can be found in [#!wall!#, Ch. 2, Thm. 6.1].

Let $q_n$ be the sequence of ``denominators'' of the partial convergents, as defined in Section 5.1.1, so $q_{-2}=1$ , $q_{-1}=0$ , and for $n\geq 0$ ,

$$q_n = a_n q_{n-1} + q_{n-2}.$$

As we saw in the proof of Theorem 5.2.6, the limit $\lim_{n\rightarrow \infty} c_n$ exists provided that the sequence $\{q_nq_{n-1}\}$ diverges to positive infinity.

For $n$ even,

$$q_n = a_n q_{n-1} + q_{n-2}$$

$$= a_n q_{n-1} + a_{n-2}q_{n-3} + q_{n-4}$$

$$= a_n q_{n-1} + a_{n-2}q_{n-3} + a_{n-4}q_{n-5} + q_{n-6}$$

$$= a_n q_{n-1} + a_{n-2}q_{n-3} + \cdots + a_2 q_{1} + q_0$$

and for $n$ odd,

$$q_n = a_n q_{n-1} + a_{n-2}q_{n-3} + \cdots + a_1 q_{0} + q_{-1}.$$

Since $a_n>0$ for $n>0$ , the sequence $\{q_n\}$ is increasing, so $q_i\geq 1$ for all $i\geq 0$ . Applying this fact to the above expressions for $q_n$ , we see that for $n$ even

$$q_n \geq a_n + a_{n-2} + \cdots + a_2,$$

and for $n$ odd

$$q_n \geq a_n + a_{n-2} + \cdots + a_1.$$

If $\sum a_n$ diverges, then at least one of $\sum a_{2n}$ or $\sum a_{2n+1}$ must diverge. The above inequalities then imply that at least one of the sequences $\{q_{2n}\}$ or $\{q_{2n+1}\}$ diverge to infinity. Since $\{q_n\}$ is an increasing sequence, it follows that $\{q_{n} q_{n-1}\}$ diverges to infinity. $\qedsymbol$

Example 5.2   Let $a_n = \frac{1}{n\log(n)}$ for $n\geq 2$ and $a_0=a_1=0$ . By the integral test, $\sum a_n$ diverges, so by Theorem 5.2.8 the continued fraction $[a_0,a_1,a_2,\ldots]$ converges. This convergence is very slow, since, e.g.

$$[a_0, a_1, \ldots, a_{9999}] = 0.5750039671012225425930\ldots$$

yet

$$[a_0, a_1, \ldots, a_{10000}] = 0.7169153932917378550424\ldots.$$

Theorem 5.2   Let $x\in\mathbb{R}$ be a real number. Then $x$ is the value of the (possibly infinite) simple continued fraction $[a_0,a_1,a_2,\ldots]$ produced by the continued fraction procedure.

Proof. If the sequence is finite then some $t_n=0$ and the result follows by Lemma 5.2.5. Suppose the sequence is infinite. By Lemma 5.2.5,

$$x = [a_0, a_1, \ldots, a_n, \frac{1}{t_n}].$$

By Proposition 5.1.5 (which we apply in a case when the partial quotients of the continued fraction are not integers!), we have

$$x = \frac{\displaystyle \frac{1}{t_n} \cdot p_n + p_{n-1}}{\displaystyle \frac{1}{t_n}\cdot q_n + q_{n-1}}.$$

Thus if $c_n=[a_0,a_1,\ldots,a_n]$ , then

$$x - c_n = x - \frac{p_n}{q_n}$$

$$=\frac{\frac{1}{t_n} p_n q_n + p_{n-1} q_n - \frac{1}{t_n} p_n q_n - p_n q_{n-1}} {q_n \left(\frac{1}{t_n} q_n + q_{n-1}\right)}.$$

$$= \frac{p_{n-1} q_n - p_{n}q_{n-1}}{q_n\left(\frac{1}{t_n} q_n + q_{n-1}\right)}$$

$$= \frac{(-1)^n}{q_n\left(\frac{1}{t_n} q_n + q_{n-1}\right)}.$$

Thus

$$\vert x - c_n\vert = \frac{1}{q_n\left(\frac{1}{t_n} q_n + q_{n-1}\right)}$$

$$< \frac{1}{q_n(a_{n+1} q_n + q_{n-1})}$$

$$= \frac{1}{q_n \cdot q_{n+1}} \leq \frac{1}{n(n+1)} \rightarrow 0.$$

In the inequality we use that $a_{n+1}$ is the integer part of $\frac{1}{t_n}$ , and is hence $\leq \frac{1}{t_n}<1$ , since $t_n<1$ . $\qedsymbol$

This corollary follows from the proof of the above theorem.

Corollary 5.2 (Convergence of continued fraction)   Let $a_0,a_1,\ldots$ define a simple continued fraction, and let $x=[a_0,a_1,\ldots]\in\mathbb{R}$ be its value. Then for all $m$ ,

$$\left\vert x - \frac{p_m}{q_m}\right\vert < \frac{1}{q_m \cdot q_{m+1}}.$$

Proposition 5.2   If $x$ is a rational number then the sequence $a_0,a_1,\ldots$ produced by the continued fraction procedure terminates.

Proof. Let $[b_0,b_1,\ldots, b_m]$ be the continued fraction representation of $x$ that we obtain using Algorithm 1.1.13, so the $b_i$ are the partial quotients at each step. If $m=0$ , then $x$ is an integer, so we may assume $m>0$ . Then

$$x = b_0 + 1/[b_1,\ldots,b_m].$$

If $[b_1,\ldots,b_m]=1$ then $m=1$ and $b_1=1$ , which will not happen using Algorithm 1.1.13, since it would give $[b_0+1]$ for the continued fraction of the integer $b_0+1$ . Thus $[b_1,\ldots,b_m]>1$ , so in the continued fraction algorithm we choose $a_0 = b_0$ and $t_0 = 1/[b_1, \ldots, b_m]$ . Repeating this argument enough times proves the claim. $\qedsymbol$