Existence of Base-N Representation

Theorem

Given a number $x \in \left[{0 .. 1}\right)$, there exists a representation of that number in a base-$p$ positional system.

Specifically, there exists a sequence $\left \langle{a_n}\right \rangle$ such that:

• $0 \le a_n < p$, and

• $\displaystyle \sum_{n=1}^\infty \frac{a_n} {p^n}$ converges to $x$.

Unless $\left \langle{a_n}\right \rangle$ terminates (i.e. $a_n = 0$ for all sufficiently large $n$), then this representation is unique.

If $\left \langle{a_n}\right \rangle$ does terminate, then there is exactly one other sequence which satisfies the criteria of the theorem.

Proof

Existence of Representation

Define $\displaystyle a_j = \left \lfloor{\left({ x-\sum_{i=1}^{j-1} \frac{a_i}{p^i} }\right) p^j} \right \rfloor$, where we accept the abuse of notation $\displaystyle \sum_{i=1}^0 a_i p^{-i} = 0$.

This recursive definition allows for all $a_n$ to be computed.

Lemma: This will always be less than $p$.

Proof: Suppose to the contrary $\exists n$ such that $a_n\geq p$.

Then:

$\displaystyle a_n = \left \lfloor{\left({x - \sum_{i=1}^{n-1} \frac{a_i}{p^i}}\right) p^n}\right \rfloor \ge p$

But then we can pull out the final term of the sum and divide by $p$ to get:

$\displaystyle \left({x - \sum_{i=1}^{n-2} \frac{a_i}{p^i}}\right) p^{n-1} \ge 1 + a_{n-1}$

This left-hand side is of course just:

$a_{n-1} + \text{something in} \ \left[{0 .. 1}\right) \ge 1 + a_{n-1}$

which is impossible.

$\Box$

Define $\displaystyle s_n = \sum_{i=1}^n a_i p^{-i}$.

Since $\forall i \in \N: a_i, p^{-i} > 0$, this series is increasing.

It is also bounded above by $x$ by construction: at every point in the series, we add precisely as many $p^{-n-1}$ as will fit in $x-s_n$ without going over $x$:

Lemma: $\forall n \in \N: s_n \le x$

Proof: We have:

$s_1 = a_1 p^{-1} = \left \lfloor{x p}\right \rfloor p^{-1} \le x p p^{-1} = x$

Suppose we have $s_j<x$ for some $j$.

By definition:

$s_{j+1} - s_j = a_{j+1} p^{-1-j}$

But:

$a_{j+1}p^{-1-j} = \left \lfloor{ \left({x - s_j}\right) p^{1+j}}\right \rfloor p^{-1-j} \le (x-s_j) $

So $s_{j+1} - s_j \le x - s_j \implies s_{j+1} \le x$.

Now suppose we have instead $s_j = x$.

Again we have $s_{j+1} - s_j = a_{j+1} p^{-1-j}$.

But now:

$a_{j+1} p^{-1-j} = \left \lfloor{\left({x-s_j}\right) p^{1+j}}\right \rfloor p^{-1-j} = 0 \implies s_{j+1} = s_j = x$

This completes the induction proof.

$\Box$

It remains to be shown this series converges to $x$.

Observe that in the sum $\displaystyle s_{k-1} + a_k p^{-k} = s_k$, we have defined $\displaystyle a_k = \left \lfloor{\left({x - \sum_{i=1}^{k-1} \frac{a_i}{p^i}}\right) p^k}\right \rfloor\ $ to count precisely how many $p^{-k}$ will fit in $x-s_{k-1}$.

We could never have $x - s_k \ge p^{-k}$ because that would mean $a_k$ had undercounted by $1$.

Therefore, $x-s_k < p^{-k}\ $.

Let $\epsilon >0$.

Then set $z = -\log_p \epsilon$.

Then $N > z \implies x - s_N < p^{-N} < p^{\log_p} \epsilon = \epsilon$.

Since $\left \langle {s_k}\right\rangle$ is increasing, bounded above by $x$, and comes arbitrarily close to $x$, we have $\left \langle{s_n}\right \rangle \to x$.

Uniqueness of Representation

Let $\left \langle {a_n}\right \rangle$ be the sequence defined in the definition of the theorem.

Let $\left \langle {b_n}\right \rangle$ be some sequence of integers $0 \le b_n < p$ such that $\left \langle {t_n}\right \rangle \to x$ where $\displaystyle t_n = \sum_{i=1}^n b_i p^{-i}$.

We wish to show that $a_n = b_n \forall n$, unless $x = q p^{-k}$ for some $k \in \N$.

Assume to the contrary that there are terms which do not agree and let $b_m$ be the first term of $\left \langle {b_n}\right \rangle$ which does not agree with $\left \langle {a_n}\right \rangle$.

Then $b_m > a_m \lor b_m < a_m$.

Let us consider the first case.

We know that $a_m $ counts precisely how many $p^{-m}$ can be added to $s_{m-1}$ without exceeding $x$.

So we can be sure that if $b_m > a_m$, then $s_{m-1} + b_m p^{-m} = t_{m-1} + b_m p^{-m} = t_m > x$.

Since $\left \langle {t_n}\right \rangle$ is always increasing, it can never converge to $x$.

Now consider the second case, $b_m < a_m$.

First, we will need a lemma:

Lemma: $\exists N \in \N : \left({\forall n \ge N: \ a_n = 0}\right) \iff \left({x = q p^{1-N}}\right)$

Proof:

($\implies$)

Suppose $\exists N : \forall n \ge N: a_n = 0$.

Then $\displaystyle x = \sum_{n=1}^\infty a_n p^{-n} = \sum_{n=1}^{N-1} a_n p^{-n}$.

But $a_n p^{-n} = a_n p^{N-1-n} p^{1-N}$.

Since $x$ is a sum of these terms of $p^{N-1}$, we must have $x = q p^{N-1}$ for some $q \in \N$.

($\ \Longleftarrow$)

Suppose $x = q p^{1-N}$.

Observe that since $p^{1-N} \backslash s_{N-1}$ (where $\backslash$ indicates divides), we must have $s_{N-1} = x$.

Since $\left \langle{s_n}\right \rangle \to x$ and is strictly increasing, we must have all successive terms equal to zero.

$\Box$

Now suppose that $x = q p^{-k}$ for some $k \in \N$.

We wish to show that there are only two series which converge to $x$:

• the series $\displaystyle \left \langle{s_n}\right \rangle = \sum_{n=1}^\infty \frac{a_n} {p^n}$ as defined above;
• another series we describe now.

Consider the sequence $\left \langle{a_n}\right \rangle$ when $x = q p^{-k}$.

Now we define:

$b_n = \begin{cases} a_n & : n < k \\ a_n - 1 & : n = k \\ p - 1 & : n > k \end{cases}$

Then we see that:

	\(\displaystyle \)	\(\displaystyle \sum_{j=1}^\infty b_j p^{-j}\)	\(=\)	\(\displaystyle \left({\sum_{j=1}^{k-1} b_j p^{-j} }\right) + (a_k-1)p^{-k} + \sum_{j=k+1}^\infty (p-1)p^{-j}\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({\sum_{j=1}^{k-1} a_j p^{-j} }\right) + a_kp^{-k}-p^{-k} + \sum_{j=k+1}^\infty (p-1)p^{-j}\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({\sum_{j=1}^{k} a_j p^{-j} }\right) - p^{-k} + \sum_{j=k+1}^\infty (p^{1-j}-p^{-j})\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle x - p^{-k} + \sum_{j=k+1}^\infty \left({p^{1-j}-p^{-j} }\right)\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle x - p^{-k} + p^{-k} \sum_{j \ge 0} \left({p^{-j} }\right) - p^{-k-1} \sum_{j \ge 0} \left({p^{-j} }\right)\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle x - p^{-k} + p^{-k} \left({\frac 1 {1 - p^{-1} } }\right) - p^{-k-1} \left({\frac 1 {1 - p^{-1} } }\right)\)	\(\displaystyle \)	Sum of Infinite Geometric Progression
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle x - p^{-k} + \frac {p^{-k} - p^{-k-1} } {1 - p^{-1} }\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle x - p^{-k} + p^{-k} \frac {1 - p^{-1} } {1 - p^{-1} }\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle x\)	\(\displaystyle \)

So, this series converges to $x$ as well.

Let us suppose, finally, that $x \ne q p^{-k}$ for any $k \in \N$.

We have already shown that if the first differing term of another series $b_n$ is greater than the corresponding term $a_n$, the sum series cannot converge to $x$.

Now we examine the case $b_m < a_m$ at the first differing term.

As we saw above, if the first term to differ is only one less, ie, $b_m = a_m-1$, then it is necessary for every other term afterwards to be increased from $0$ to $p-1$ in order to make up for this deficit.

The remaining terms of course, cannot be increased more than this, or they would violate the condition that all terms be less than $p$.

Since in the case $x \ne q p^{-k}$, there are no infinite strings of zeroes, we cannot decrease any one term and increase the succeeding terms by $p - 1$.

$\blacksquare$

Also see

• Basis Expansion for how this applies to the representation of a real number

• Basis Representation Theorem for an equivalent proof for integers.