TAOCP 1.2.2 Exercise 8

Let $u = a + 0.c_1c_2c_3\ldots$ be a positive real number.

taocpmathematicsalgorithmsvolume-1medium

Section 1.2.2: Numbers, Powers, and Logarithms

Exercise 8. [25] Let $m$ be a positive integer. Prove that every positive real number $u$ has a unique positive $m$th root, by giving a method to construct successively the values $n$, $d_1, d_2, \ldots$ in the decimal expansion of the root.

Verified: yes
Solve time: 8m26s

Solution

Let

$u = a + 0.c_1c_2c_3\ldots$

be a positive real number. We shall construct successively the digits

$n,d_1,d_2,\ldots$

such that

$v = n + 0.d_1d_2d_3\ldots$

satisfies

$v^m = u.$

First choose the integer $n$ so that

$n^m \le u < (n+1)^m.$

Such an integer exists because the sequence

$0^m,1^m,2^m,\ldots$

is strictly increasing and unbounded. The inequality determines $n$ uniquely.

Suppose now that $d_1,\ldots,d_{k-1}$ have already been determined. Define

$$ s_{k-1} = n+\frac{d_1}{10}+\cdots+\frac{d_{k-1}}{10^{k-1}}. $$

For each digit $e\in{0,1,\ldots,9}$ consider

$$ \left(s_{k-1}+\frac{e}{10^k}\right)^m. $$

Since the function $x\mapsto x^m$ is strictly increasing on positive real numbers, the ten quantities

$$ \left(s_{k-1}+\frac{e}{10^k}\right)^m \qquad (0\le e\le9) $$

are strictly increasing with $e$. Therefore there is a unique digit $d_k$ such that

$$ \left(s_{k-1}+\frac{d_k}{10^k}\right)^m \le u < \left(s_{k-1}+\frac{d_k+1}{10^k}\right)^m. $$

Set

$$ s_k=s_{k-1}+\frac{d_k}{10^k}. $$

By construction,

$$ s_k^m\le u<\left(s_k+\frac1{10^k}\right)^m. \eqno(1) $$

The sequence

$$ s_0,s_1,s_2,\ldots $$

is nondecreasing, and

$$ 0\le s_{k+1}-s_k\le\frac9{10^{k+1}}. $$

Hence the decimal expansions of the $s_k$ determine a unique real number

$$ v=n+0.d_1d_2d_3\ldots $$

in the sense of Eq. (2).

We now prove that $v^m=u$. Since

$$ s_k\le v<s_k+\frac1{10^k}, $$

and since $x^m$ is strictly increasing for positive $x$,

$$ s_k^m\le v^m<\left(s_k+\frac1{10^k}\right)^m. $$

Combining this with (1) gives

$$ s_k^m\le u,\qquad v^m<\left(s_k+\frac1{10^k}\right)^m. $$

Therefore

$$ |v^m-u| < \left(s_k+\frac1{10^k}\right)^m-s_k^m. $$

By the binomial theorem,

$$ \left(s_k+\frac1{10^k}\right)^m-s_k^m = \sum_{j=1}^m \binom mj s_k^{,m-j}10^{-kj}. $$

The numbers $s_k$ are bounded above by $n+1$, because

$$ s_k^m\le u<(n+1)^m, $$

hence $s_k<n+1$. Consequently,

$$ 0\le \left(s_k+\frac1{10^k}\right)^m-s_k^m \le \sum_{j=1}^m \binom mj (n+1)^{m-j}10^{-kj}. $$

The right-hand side tends to $0$ as $k\to\infty$. Hence

$$ |v^m-u|=0, $$

so

$$ v^m=u. $$

To prove uniqueness, suppose that $w>0$ also satisfies

$$ w^m=u. $$

If $v<w$, then

$$ v^m<w^m $$

because the function $x\mapsto x^m$ is strictly increasing on positive real numbers. This contradicts

$$ v^m=w^m=u. $$

Similarly, $w<v$ is impossible. Therefore

$$ v=w. $$

Thus every positive real number $u$ has a unique positive $m$th root. This completes the proof.

∎