Existence of n-th Roots

For $a > 0$ and a natural number $n$ , let $E = \{x \ge 0 : x^n < a\}$ . Show $E$ is nonempty and bounded above, and with $s = \sup E$ prove completely by trichotomy that $s^n = a$ .

E = \{x \ge 0 : x^n < a\}, \qquad s = \sup E, \qquad s^n = a

a = 2

,

n = 2

: the shaded region is

E = \{x \ge 0 : x^2 < 2\}

, and its supremum

s = \sup E

sits at the vertical dashed line,

\sqrt{2} \approx 1.41421356

. The proof below shows this

s

is exactly the square root of

a

.

Show proof

$E$ is nonempty: $0^n = 0 < a$ , so $0 \in E$ . And $a + 1$ is an upper bound of $E$ : if $x > a + 1$ then, since $a > 0$ , $x > 1$ , hence $x^n \ge x > a + 1 > a$ , so $x \notin E$ .
By completeness of the reals (the least-upper-bound axiom), $s = \sup E$ exists. We have $s \ge 0$ ; we show $s^n = a$ by trichotomy: ruling out $s^n < a$ and $s^n > a$ leaves $s^n = a$ .
Suppose $s^n < a$ . For $\delta > 0$ , the binomial theorem gives $(s+\delta)^n - s^n = \sum_{k=1}^{n}\binom{n}{k}s^{n-k}\delta^k = \delta\sum_{k=1}^{n}\binom{n}{k}s^{n-k}\delta^{k-1}$ . For $0 < \delta < 1$ , $\delta^{k-1} \le 1$ , so this difference is at most $\delta M$ , where $M = \sum_{k=1}^{n}\binom{n}{k}(s+1)^{n-k}$ depends only on $s$ . Picking $0 < \delta < \min(1, (a - s^n)/M)$ gives $(s+\delta)^n < s^n + (a - s^n) = a$ , and $s + \delta \ge 0$ , so $s + \delta \in E$ — contradicting $s$ being an upper bound.
Suppose $s^n > a$ . Since $a \ge 0$ , $s > 0$ . For $0 < \delta < s$ , put $t = s - \delta$ ; the factorization $s^n - t^n = (s-t)(s^{n-1} + s^{n-2}t + \cdots + t^{n-1})$ gives $s^n - (s-\delta)^n = \delta\sum_{j=0}^{n-1}s^{n-1-j}t^j \le n\,\delta\,s^{n-1}$ (each term is at most $s^{n-1}$ since $t \le s$ ). Picking $0 < \delta < \min(s, (s^n - a)/(n s^{n-1}))$ yields $(s-\delta)^n > a$ . But every $x \ge s - \delta$ satisfies $x^n \ge (s-\delta)^n > a$ , so $x \notin E$ — i.e. $s - \delta$ is also an upper bound of $E$ , contradicting $s$ being the least upper bound.
Hence $s^n = a$ , and since $s \ge 0$ , $s$ is the nonnegative $n$ -th root of $a$ . (Uniqueness is the next problem.) This proof grabs the continuity of $x^n$ by hand through the binomial expansion — an argument that works precisely because the least-upper-bound axiom guarantees a "hole-free" real line.

Prove that if $s, t \ge 0$ and $s^n = t^n = a$ , then $s = t$ — the nonnegative $n$ -th root is unique.

t^n - s^n = (t-s)(t^{n-1} + t^{n-2}s + \cdots + s^{n-1})

a = 2

,

n = 2

: the vertical dashed line is drawn at a single point,

\sqrt{2} \approx 1.41421356

— there is exactly one nonnegative number squaring to

2

.

Show proof

Suppose $0 \le s < t$ . In the factorization $t^n - s^n = (t-s)(t^{n-1} + t^{n-2}s + \cdots + s^{n-1})$ , the first factor $t - s > 0$ , and each term of the second factor is nonnegative and not all zero (in particular $t^{n-1} > 0$ , since $t > 0$ ). Hence $t^n - s^n > 0$ , i.e. $s^n < t^n$ : $x^n$ is strictly increasing on $[0, \infty)$ .
If $s^n = t^n = a$ with $s \ne t$ , then by symmetry $s < t$ or $t < s$ , and the above gives $s^n \ne t^n$ — a contradiction. Hence $s = t$ : the nonnegative $n$ -th root is unique.

When approximating the $n$ -th root of $a$ by bisection, prove the error bound $|x_k - s| \le \frac{b_0 - a_0}{2^k}$ for the $k$ -th midpoint $x_k$ , and verify it numerically by computing 10 steps for $a = 2$ , $n = 2$ .

\lvert x_k - s\rvert \le \frac{b_0 - a_0}{2^k}, \qquad x_{10} = 1.416015625

\lvert x_{10} - \sqrt{2}\rvert \approx 0.0018021 < \frac{2}{2^{10}} = 0.001953125

a = 2

,

n = 2

: 60 bisection iterations give

\sqrt{2} \approx 1.41421356

(

|\text{diff}| \approx 2.2\times 10^{-16}

). Below, the error bound is checked directly at 10 steps.

Show proof

Start from $[a_0, b_0] = [0, \max(1, a)]$ : $a_0^n - a = -a < 0 \le b_0^n - a$ , so the (unique) root $s$ lies inside. At each step, at the midpoint $m$ , if $m^n < a$ discard the left half ( $s > m$ ), else discard the right ( $s \le m$ ) — the sign brackets $s$ , so the invariant $s \in [a_k, b_k]$ is preserved and the length halves each time: $b_k - a_k = \frac{b_0 - a_0}{2^k}$ .
Since $x_k = \frac{a_k + b_k}{2}$ is the midpoint and $s$ lies in the same interval, $|x_k - s| \le \frac{b_k - a_k}{2} = \frac{b_0 - a_0}{2^{k+1}} \le \frac{b_0 - a_0}{2^k}$ . (Counting steps from 1 gives exactly $\frac{b_0-a_0}{2^k}$ .) The error at least halves every step.
For $a = 2$ , $n = 2$ , $[a_0, b_0] = [0, 2]$ , so the bound is $\frac{2}{2^k}$ . Running 10 steps by hand gives $x_{10} = 1.416015625$ and $|x_{10} - \sqrt{2}| \approx 0.0018021$ — inside the bound $\frac{2}{2^{10}} = \frac{1}{512} \approx 0.0019531$ . The model's 60-iteration value $1.414213562373095$ agrees with $\sqrt{2}$ to within $2.3\times 10^{-16}$ .

Examples & Exercises