Explicitness in numeral system

Question

Prove that for every $a\in\mathbb{N}$ there is one and only one way to express it in the system with base $\mathbb{N}\ni s>1$.

Seems classical, but I don't have any specific argument.

Answer 1

Suppose that some positive integer $N$ has two representations base $s$. Then we can write $$N=\sum_{k=0}^ma_ks^k=\sum_{k=0}^nb_ks^k\;,\tag{1}$$ where $0\le a_1,\dots,a_m,b_1,\dots,b_n\le s-1$ are integers, and without loss of generality we may assume that $m\le n$.

Suppose first that $m<n$. Then

$$\begin{align*} \sum_{k=0}^ma_ks^k&\le\sum_{k=0}^m(s-1)s^k\\ &=\sum_{k=0}^ms^{k+1}-\sum_{k=0}^ms^k\\ &=\sum_{k=1}^{m+1}s^k-\sum_{k=0}^ms^k\\ &=s^{m+1}-1\\ &<s^n\\ &\le\sum_{k=0}^nb_ks^k\;, \end{align*}$$

contradiction the assumption $(1)$. Thus, we assume that $m=n$.

Now make the further assumption that $N$ is the smallest positive integer with two different base $s$ representations. Without loss of generality assume that $a_n\le b_n$, and let $M=N-a_ns^n$. Then

$$M=\sum_{k=0}^{n-1}a_ks^k=\sum_{k=0}^{n-1}b_ks^k+(b_n-a_n)s^n\;.\tag{2}$$

We just proved that this is impossible if $b_n-a_n\ne 0$, so $(2)$ must simplify to

$$M=\sum_{k=0}^{n-1}a_ks^k=\sum_{k=0}^{n-1}b_ks^k\;.$$

But then $M$ is a number with two base $s$ representations that is smaller than $N$, contradicting our choice of $N$. It follows that no such $N$ exists and hence that every positive integer has a unique representation base $s$.

Answer 2

We can express a natural number $a$ to any base $s$ by writing $k = \lceil \log_s a \rceil$, the number of digits we'll need, $a_k=\max(\{n\in \mathbb{N}: ns^k\leq a\}),$ and recursively $a_{i}=\max(\{n\in \mathbb{N}: ns^i \leq a-\sum_{j=i+1}^k a_j s^j\})$. It's immediate that each of these maxes exists, since $0s^i\leq a$ no matter what and $a s^i\geq a$, and that they're unique by, say, the well-ordering of $\mathbb{N}$. Then $$a=\sum_{j=0}^k a_j s^k$$

Answer 3

We show existence by (strong) induction. Suppose the result is true for all $m\lt n$. Show it is true at $n$.

Let $s^k$ be the largest power of $s$ that is $\le n$. Then $1\le n/s^k \lt s$. So if $d=\lfloor n/s^k\rfloor$ then $s=ds^k +m$ where $0\le m\lt n$ and $m\lt s^k$. If $m=0$ we are finished, else apply induction hypothesis.

For uniqueness, again we can use induction. The lead digit is uniquely determined by the condition in the preceding paragraph.

Another way: Uniqueness is particularly easy to prove by an induction running in the other direction. Take a particular representation, of a possible several. The "units" digit $d_0$ is uniquely determined as the remainder when $n$ is divided by $s$. But then the next digit $d_1$ is the remainder when $(n-d_0)/s$ is divided by $s$. This is determined completely by $n$. But then the next digit is the remainder when $(n-d_0-d_1s)/s^2$ is divided by $s$, again completely determined by $n$. And so on.

Existence can be proved in the same way. Let $d_0$ be the remainder when $n$ is divided by $s$. Then $n=ms+d_0$, and by induction hypothesis $m$ has a representation.

Answer 4

This is a variation of "another way" by André Nicolas, proving existence and existence at uniqueness at the same time. The main reason I write this answer is that I feel that any complete proof should explicitly use in the uniqueness part the fact that a leading digit "$0$" is forbidden, and in the existence part that $s>1$. So the statement to prove is:

For $s\in\mathbb N$ with $s>1$ and any $a\in\mathbb N$ there exists a unique sequence $(a_{k-1},\ldots,a_0)$ with $k\in\mathbb N$ and $a_i\in\{0,\ldots,s-1\}$ for $0\leq i<k$, and $a_{k-1}\neq0$ if $k>0$, such that $a=\sum_{0\leq i<k}a_is^i$.

For all $n>0$ one has $sn>n$ (since $s>1$) so for every $m>0$ the quotient $\lfloor\frac ms\rfloor$ of the Eucliedean division of $m$ by $s$ is strictly smaller than $m$; this will allow us to do a strong induction on $a$ in which the induction hypothesis applies to $\lfloor\frac as\rfloor$.

The case $a=0$ needs separate consideration; the empty sequence ($k=0$) is a solution, and it is unique since for any sequence with $k>0$ the requirement $a_{k-1}\neq0$ implies $\sum_{0\leq i<k}a_is^i>0$. Now assume $a>0$ and by strong induction that the unique existence has been proved for $q=\lfloor\frac as\rfloor$. Writing $a=sq+r$ one has $r=a\bmod s$ (the remainder of Euclidean division) and for any solution $a=\sum_{0\leq i<k}a_is^i$, now obviously with $k>0$, one has $a\equiv a_0\pmod s$; therefore $a_0=r$ by the requirement $a_0\in\{0,\ldots,s-1\}$. Given that fact, the condition $a=\sum_{0\leq i<k}a_is^i$ is equivalent to $\sum_{1\leq i<k}a_is^{i-1}=\lfloor\frac as\rfloor=q$, which by the induction hypothesis has a unique solution $(a_{k-1},\ldots,a_1)$. If $k=1$ one has $a_{k-1}=a_0=a\neq0$ by assumption, and if $k>1$ then $a_{k-1}\neq0$ is part of the requirement for a solution for $q$.