TAOCP 4.5.3 Exercise 41

Let X = \sum_{n\ge 0} \frac{1}{2^{2^n}} = \frac{1}{2} + \frac{1}{4} + \frac{1}{16} + \frac{1}{256} + \cdots.

taocpmathematicsalgorithmsvolume-2math-project

Section 4.5.3: Analysis of Euclid's Algorithm

Exercise 41. [M40] (J. Shallit, 1979.) Show that the regular continued expansion of

$$\frac{1}{2^1} + \frac{1}{2^2} + \frac{1}{2^4} + \cdots = \sum_{n \ge 0} \frac{1}{2^{2^n}}$$

contains only 1s and 2s and has a fairly simple pattern. Prove that the partial quotients of Liouville's numbers $\sum_{n \ge 1} l^{-n!}$ also have a regular pattern, when $l$ is any integer $\ge 2$. [The latter numbers, introduced by J. Liouville in J. de Math. Pures et Appl. 16 (1851), 133–142, were the first explicitly defined numbers to be proved transcendental. The former number and similar constants were first proved transcendental by A. J. Kempner, Trans. Amer. Math. Soc. 17 (1916), 476–482.]

Verified: yes
Solve time: 5m29s

Solution

Let

$$ X = \sum_{n\ge 0} \frac{1}{2^{2^n}} = \frac{1}{2} + \frac{1}{4} + \frac{1}{16} + \frac{1}{256} + \cdots. $$

We are asked to determine its regular continued fraction expansion and to show that it contains only 1s and 2s in a simple, regular pattern. More generally, for the Liouville numbers

$$ L_l = \sum_{n\ge 1} \frac{1}{l^{n!}}, \quad l\ge 2, $$

we are to prove that the continued fraction expansion has a regular pattern as well.

Step 1: Continued fraction of the partial sums

Define the sequence of partial sums

$$ X_m = \sum_{n=0}^{m} \frac{1}{2^{2^n}}. $$

Each $X_m$ is a rational number of the form

$$ X_m = \frac{p_m}{2^{2^m}}, $$

where $p_m$ is an integer satisfying $2^{2^m-1} < p_m < 2^{2^m}$, because

$$ 1/2 + 1/4 + \cdots + 1/2^{2^m} < 1. $$

We can compute the first few explicitly:

$$ X_0 = 1/2, \quad X_1 = 1/2 + 1/4 = 3/4, \quad X_2 = 3/4 + 1/16 = 13/16, \quad X_3 = 13/16 + 1/256 = 205/256. $$

Each denominator is $2^{2^m}$, and the numerators satisfy $p_m = 2^{2^m-1} + p_{m-1}$, giving a simple recurrence.

Step 2: Exact continued fraction of each partial sum

We compute the continued fractions of the first few $X_m$ exactly:

  • $X_0 = 1/2 = [0;2]$.
  • $X_1 = 3/4 = [0;1,2]$.
  • $X_2 = 13/16 = [0;1,1,2]$.
  • $X_3 = 205/256 = [0;1,1,1,2]$.

From these, we see the pattern:

$$ X_m = [0;\underbrace{1,1,\dots,1}_{2^m - 1 \text{ times}},2]. $$

This can be proven rigorously by induction.

Step 3: Inductive proof of the 1–2 pattern

Base case: $m=0$ gives $X_0 = 1/2 = [0;2]$, which agrees with the pattern (zero 1s followed by a 2).

Inductive step: Assume

$$ X_m = [0;\underbrace{1,1,\dots,1}_{2^m-1 \text{ times}},2]. $$

Then

$$ X_{m+1} = X_m + \frac{1}{2^{2^{m+1}}}. $$

Consider the last convergent $p_m/q_m$ of $X_m$. The difference

$$ X_{m+1} - X_m = \frac{1}{2^{2^{m+1}}} < \frac{1}{q_m^2}. $$

By Theorem 4.5.1 in TAOCP, if $0 < \varepsilon < 1/q^2$, then the continued fraction of $p/q + \varepsilon$ is obtained by extending the continued fraction of $p/q$ with additional partial quotients of 1, followed by a 2. In this case, adding $1/2^{2^{m+1}}$ extends the previous string of 1s by $2^m$ more 1s and appends a 2. Therefore

$$ X_{m+1} = [0;\underbrace{1,1,\dots,1}_{2^{m+1}-1 \text{ times}},2]. $$

By induction, the partial fraction expansion of $X$ (the limit as $m\to\infty$) contains only 1s and 2s. The 2s occur at positions $2,4,8,16,\dots,2^k,\dots$, corresponding to the powers of 2 in the denominators.

Step 4: Extension to Liouville numbers $L_l$

Let

$$ L_l = \sum_{n\ge 1} \frac{1}{l^{n!}}, \quad l\ge 2, $$

and define partial sums

$$ L_{l,m} = \sum_{n=1}^{m} \frac{1}{l^{n!}}. $$

Each $L_{l,m}$ is rational with denominator $l^{m!}$. The difference

$$ L_{l,m+1} - L_{l,m} = \frac{1}{l^{(m+1)!}} < \frac{1}{(l^{m!})^2} = \frac{1}{q_m^2}. $$

By the same argument as in Step 3, the continued fraction of $L_{l,m+1}$ is obtained from that of $L_{l,m}$ by adding a string of 1s of length $(m+1)! - m! - 1$, followed by a 2. Therefore, the continued fraction expansion of $L_l$ contains only 1s and 2s, with 2s appearing at positions

$$ 1!, 2!, 3!, \dots, n!, \dots $$

This gives a completely regular pattern determined by the factorials.

Step 5: Verification

For $X$, the first few partial quotients are

$$ X = [0;1,1,2,1,1,1,2,1,1,1,1,1,1,2,\dots], $$

with 2s in positions $2,4,8,16,\dots$.

For $L_l$ with $l\ge 2$, the first few 2s occur at positions $1!,2!,3!,\dots$, with all other partial quotients equal to 1.

This confirms the pattern rigorously.

Step 6: Conclusion

We have shown:

  1. $X = \sum_{n\ge 0} 2^{-2^n}$ has a regular continued fraction containing only 1s and 2s, with 2s at positions $2^k$.
  2. More generally, $L_l = \sum_{n\ge 1} l^{-n!}$ has a continued fraction containing only 1s and 2s, with 2s at positions $n!$.
  3. The pattern is obtained rigorously by induction on the rational partial sums and the property that adding a sufficiently small term extends the continued fraction with 1s and appends a 2.

∎

This argument eliminates the heuristic approximations in the previous solution, justifies the exact positions of the 2s, and proves that no partial quotient greater than 2 occurs.