existence and uniqueness of decimal expansion

The existence and uniqueness of decimal expansions (or more generally, base-$b$ expansions) is taken for granted by most grade school students, but they are facts that need to be rigorously proven if one wants to understand the real numbers thoroughly.

We mention the following fact about natural numbers $n,m\in\mathbb{N}_{0}$, which we will use many times implicitly:

 $n

This fact can be proven by mathematical induction on $m$.

1 Proof of Existence

Let $x$ be a number for which we want to write a base-$b$ expansion for any natural number $b$ greater than one.

We shall assume $x\geq 0$, since the base-$b$ expansion of a negative number is by definition the negative of the expansion for its absolute value.

1.1 Expansions for non-negative integers

First we prove the existence of expansions of the form

 $x=\sum_{i=0}^{k}a_{i}b^{i}\,,\quad 0\leq a_{i}

for non-negative integers $x$, using mathematical induction. (This proof is essentially the formal statement of how to do addition by base-$b$ digits.)

The number $x=0$ obviously has the expansion $0$.

Suppose that we know the existence of expansions for a number $x-1$. We prove the existence of an expansion for $x$.

Let $x-1$ be expanded as

 $x-1=\sum_{i=0}^{k}a_{i}b^{i}\,,\quad 0\leq a_{i}

From the above equation, add $1$ to both sides:

 $x=(a_{0}+1)+\sum_{i=1}^{k}a_{i}b^{i}\,.$

If $a_{0}, then we are done. Otherwise, $(a_{0}+1)=b$, and therefore we may write instead

 $x=0+(a_{1}+1)b+\sum_{i=2}^{k}a_{i}b^{i}\,.$

If $a_{1}, then we can stop. Otherwise, repeat the process and continue carrying digits until we reach some $i$ for which $a_{i}. Since $a_{k+1}=0$, this process is guaranteed to stop. At the end we will have expressed $x$ in base $b$.

1.2 Reduction to numbers in $[0,1)$

Let $\lfloor x\rfloor$ be the greatest integer less than or equal to $x$, otherwise known as the floor of $x$. We prove that the floor of $x$ exists.

The set

 $A=\{n\in\mathbb{N}_{0}\colon n\leq x\}$

is bounded above by $x$. However, by the Archimedean property, the set of natural numbers is not bounded above, so $\mathbb{N}_{0}\setminus A$ must be non-empty, and have a smallest element $u$ (formally, by the well-ordering principle). For every $n\in A$, we have $n\leq x. The latter condition is equivalent to $n\leq u-1, so $u-1$ is the maximum element of $A$. In other words, $\lfloor x\rfloor=u-1$.

Since $u-1\leq x, we have $0\leq x-\lfloor x\rfloor<1$. We shall obtain the base $b$ expansion of $x$ as the sum of the expansion of $\lfloor x\rfloor$ and $x-\lfloor x\rfloor$.

1.3 Expansion of numbers in $[0,1)$

Given $x\in[0,1)$, let $a_{1}=\lfloor bx\rfloor$. Then $0\leq a_{1}\leq bx, so we can take $a_{1}$ as the first digit of the base-$b$ expansion of $x$. Next, write

 $x=a_{1}b^{-1}+yb^{-1}\,,$

and observe that $0\leq x-a_{1}b^{-1}=b^{-1}(bx-\lfloor bx\rfloor), so it is possible to get the next digit of the expansion by expanding $y$. We do this recursively, leading to these recursive relations:

 $y_{i}=a_{i}b^{-1}+y_{i+1}b^{-1}\,,\quad 0\leq a_{i}=\lfloor by_{i}\rfloor

More explicitly, we have

 $\displaystyle x-(a_{1}b^{-1}+a_{2}b^{-2}+\cdots+a_{k}b^{-k})$ $\displaystyle=b^{-1}\bigl{(}y_{2}-(a_{2}b^{-1}+\cdots+a_{k}b^{-k+1})\bigr{)}$ $\displaystyle=b^{-2}\bigl{(}y_{3}-(a_{3}b^{-1}+\cdots+a_{k}b^{-k+2})\bigr{)}$ $\displaystyle=\cdots$ $\displaystyle=b^{-k+1}(y_{k}-a_{k}b^{-1})$ $\displaystyle=b^{-k}y_{k+1}\,.$

It is easy to prove that the expansion

 $a_{1}b^{-1}+a_{2}b^{-2}+\cdots+a_{k}b^{-k}+\cdots$

converges to $x$:

 $0\leq x-\sum_{i=1}^{k}a_{i}b^{-i}=b^{-k}y_{k+1}<\frac{1}{b^{k}}\to 0\,,\quad% \text{as k\to\infty.}$

(Formally, the “$\to 0$” part appeals to the Archimedean property.)

2 Proof of uniqueness

2.1 Uniqueness for non-negative integers

Suppose that

 $x=\sum_{i=0}^{k}a_{i}b^{i}\,,\quad 0\leq a_{i}

Now

 $a_{k}b^{k}\leq\sum_{i=0}^{k}a_{i}b^{i}\leq a_{k}b^{k}+\sum_{i=0}^{k-1}(b-1)b^{% i}=a_{k}b^{k}+(b^{k}-1)<(a_{k}+1)b^{k}\,,$

and the intervals $[a_{k}b^{k},(a_{k}+1)b^{k})$ are disjoint for each value of $a_{k}$, so $a_{k}$ is uniquely determined by where $x$ lies in amongst these intervals.

Then we can consider

 $x-a_{k}b^{k}=\sum_{i=0}^{k-1}a_{i}b^{i}\,.$

Repeating the previous argument with $k$ replaced by $k-1$, we see that $a_{k-1}$ is uniquely determined. Then we can consider $x-a_{k}b^{k}-a_{k-1}b^{k-1}$ and so on. Continuing this way, we see that all the digits $a_{i}$ are uniquely determined.

2.2 Near-uniqueness for non-negative numbers

If

 $x=a_{k}b^{k}+\cdots+a_{1}b+a_{0}+a_{-1}b^{-1}+a_{-2}b^{-2}+\cdots$

then $a_{0},\ldots,a_{k}$ are uniquely determined, since $a_{k}b^{k}+\cdots+a_{1}+a_{0}$ is the expansion for the non-negative integer $\lfloor x\rfloor$.

The argument to prove that $a_{-i}$ are uniquely determined proceeds similarly as before. We have

 $\displaystyle a_{-1}b^{-1}$ $\displaystyle\leq a_{-1}b^{-1}+a_{-2}b^{-2}+\cdots$ $\displaystyle\leq a_{-1}b^{-1}+\sum_{i=2}^{\infty}(b-1)b^{-i}$ (geometric series) $\displaystyle=a_{-1}b^{-1}+\frac{(b-1)b^{2}}{1-b^{-1}}$ $\displaystyle=(a_{-1}+1)\,b^{-1}\,,$

where equality on the second line occurs if and only if $a_{-i}=b-1$ for every $i\geq 2$. If we insist that $a_{-i}$ is never eventually the same digit $b-1$, then this shows that the digit $a_{-1}$ is uniquely determined by where the original number $x$ in the disjoint intervals $[a_{-1}b^{-1},(a_{-1}+1)b^{-1})$.

This argument may be repeated, to show that $a_{-i}$ are uniquely determined, under the assumption that the expansion does not end in all digits being $b-1$.

If the assumption is not made, then numbers which have an expansion ending in all digits $0$ have an alternate expansion ending in all digits $b-1$, but other numbers still have unique base-$b$ expansions.

3 Every base-$b$ expansion represents a real number

We also want to prove that for every sequence of digits $a_{k},a_{k-1},\ldots,a_{1},a_{0},a_{-1},a_{-2},\ldots$ there exists a real number $x$ with the base-$b$ expansion

 $x=\sum_{i=0}^{k}a_{i}b^{i}+\sum_{i=0}^{\infty}a_{-i}b^{-i}\,.$

This is the where we use the least upper bounds property of the real numbers. (So far we have only used the Archimedean property, so what we have done so far is also valid for $\mathbb{Q}$.)

Consider the sequence $\{s_{n}\}$ with the

 $s_{n}=\sum_{i=0}^{k}a_{i}b^{i}+\sum_{i=0}^{n}a_{-i}b^{-i}\,.$

This sequence, considered as a set, is bounded above, for $s_{n}\leq a_{k}b^{k}+\cdots+a_{0}+1$. So it has a least upper bound $x$. Since the sequence $\{s_{n}\}$ is also increasing, its least upper bound is the same as its limit.

Title existence and uniqueness of decimal expansion ExistenceAndUniquenessOfDecimalExpansion 2013-03-22 15:42:12 2013-03-22 15:42:12 stevecheng (10074) stevecheng (10074) 8 stevecheng (10074) Theorem msc 11A99 every decimal expansion represents a real number CantorsDiagonalArgument DecimalExpansion