Existence & uniqueness of radix representation by decrementing descent

Question

I'm reading a proof in George E. Andrew's Number Theory of the Basis Representation Theorem (i.e. each positive integer $n$ has a unique representation in base $k$), and I'm having some difficulty. For reference, the argument in the proof runs like this:

Suppose we have a representation of $n$ as $$n = a_0k^s + a_1k^{s-1} + ... + a_{s}.$$

If some of the trailing $a_i$ are $0$, then exclude them so that $$n = a_0k^s + a_1k^{s-1} + ... + a_{s-t}k^t,$$ where now $a_0 \neq 0$ and $a_{s-t} \neq 0$. Then $$ \begin{align*} n-1 &= a_0k^s + a_1k^{s-1} + ... + a_{s-t}k^t - 1\\ &= a_0k^s + a_1k^{s-1} + ... + (a_{s-t}-1)k^t + k^t - 1\\ &= a_0k^s + a_1k^{s-1} + ... + (a_{s-t}-1)k^t + \sum_{j=0}^{t-1}(k-1)k^j. \end{align*} $$

Let $b_k(n)$ denote the number of representations of $n$ in the base $k$. We just showed that for every representation of $n$, we can find one for $n-1$, so that $$b_k(n) \leq b_k(n-1).$$

With this fact, the proof continues and concludes $$1 \leq b_k(k^n) \leq b_k(n) \leq b_k(1) = 1, \ \ \ (1.1)$$

So we have existence and uniqueness. $\blacksquare$

My question: Part of the theorem's hypothesis says each $a_i$ is such that $0 \leq a_i \leq k-1$. I want to understand where the proof fails if you remove this requirement. If you allow $a_i$'s to be negative, then I see why the proof fails, because then $1$ can be expressed in numerous ways, so that $b_k(1) \neq 1$ (for example $1 = -(k-1)\cdot k^0 + 1\cdot k^1$). However, I don't see where the proof fails in the case where you require $a_i \geq 0$, but allow them to be arbitrarily large (i.e. $0 \leq a_i < \infty)$. In this case, $1$ still has a unique representation, so the problem lies somewhere in the left side of $(1.1)$ rather than the right side. I can see the issue with a particular example: if you allow arbitrarily large $a_i$, then you could have for instance $3 = 1\cdot3^1 = 3*3^0$, so that $b_3(3) = 2$, while $b_3(1) = 1$, so $b_3(3) > b_3(1) = 1$, which is the opposite of the inequality $b_k(n) \leq b_k(n-1)$ in the proof, but I don't see how the proof fails in this case. I'm rather confused, so insights would be appreciated.

Answer 1

If you allow digits greater than $k-1$, then uniqueness fails like this:

In base $5$, let's represent the number $6$. We can write it as:

$11_5$

or as

$6_5$

This is why we don't have a digit for $6$, in base $5$, but if we did, we would lose uniqueness.

Answer 2

The issue is that different representations of $n$ can result in the same representation for $n-1$ if $a_i$ is allowed to be any nonnegative integer. For example, allowing for such $a_i$ but following the process Andrews describes we find $$\begin{array}{rcll} 10 = 1\cdot 10^1 &\rightarrow& 9 = (1-1) 10^1 + (10-1) 10^0 = 9\cdot 10^0 &\\ 10 = 10\cdot 10^0 &\rightarrow& 9 = (10-1) 10^0 = 9\cdot 10^0. &\quad(!) \end{array}$$ Thus, it does not follow that $b_k(n)\le b_k(n-1)$. It is critical to Andrews' argument that different representations of $n$ result in different representations for $n-1$. This only occurs if $0\le a_i\le k-1$.