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.
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.
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
, and $a_{k-1}\neq0$ if $k>0$, such that $a=\sum_{0\leq 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
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$
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
$\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\\ &
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$.
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.