Help to understand proof for any positive integer to be used as a base.

Question

Help needed for alternate proof, & understand proof for any positive integer to be used as a base.

Problem statement:
Let $g$ be a positive integer $\gt 1$. Then every positive $a$ can be written uniquely in the form $$a = c_ng^n+\ldots+c_g+c_0, -(1)$$ where $n\ge 0$, $c_i$ is an integer, $0\le c_i \lt g$, $c_n\ne 0$. $g$ is called the base of $a,$ which is denoted by $(c_nc_{n-1}\ldots c_1c_0)_g$.

Proof: Using induction on $a$. When $a=1$, have $n=0$ & $c_0=1$. So true for $a=1$.
Now assume that the theorem is true for any integer less than $a$. Since $g\gt 1, a\gt 0, a$ must lie between two certain consecutive numbers of the following sequence:
$$g^0,g^1,g^2,\ldots,g^n,\ldots$$ More explicitly, there is a unique integer $n,$ s.t. $$g^n\le a\lt g^{n+1}$$ By divisibility theorem, can state: $$a=c_ng^n+r, 0\le r\lt g^n,$$ obviously, $g\gt c_n \gt 0$. If $r=0$, then $$a=c_ng^n+0g^{n-1}+\ldots +0g+0.$$ If $r\ne 0$, by induction hypothesis $$r=b_tg^t+\ldots+b_g+b_0, t\lt n,$$ where $0\le b_i \lt g.$ Thus $$a=c_ng^n+b_tg^t+\ldots+b_1g+b_0,$$ and the given statement $(1)$ is true.

---

To prove the uniqueness, assume there is another representation $$a=d_mg^m+\ldots+d_1g+d_0,-(2)$$ with $m\ge 0, 0\le d_i\lt g.$ If $c_i$ & $d_i$ are not all equal, by subtracting $(1)$ from $(2)$, get $$0=e_sg^s+\ldots +e_1g+e_0,$$ where $s$ is the largest value of $i$ for which $c_i\ne d_i,$ so that $e_s\ne 0$. If $s=0$, then $c_1=c_0=0$, which is a contradiction. If $s\gt 0$, $$|e_i|=|c_i-d_i|\lt g-1, i=0,\ldots, s-1,$$ and $$e_sg^s=-(e_{s-1}g^{s-1}+\ldots+e_0),$$ so that $$g^s\lt |e_sg^s|=|e_{s-1}g^{s-1}+\ldots+e_0| \lt (g-1)(g^{s-1}+\ldots+g+1)= g^s -1,$$ which is also a contradiction. Thus conclude $$n=m, c_i=d_i, i=0,1,\ldots,n,$$ as well as the representation is unique.

---

I feel that the inductive proof is unclear on how it has used the second step (i.e., is true for any value for $n=n'$) of weak-induction to get to the final step.
Also, the proof part for showing uniqueness is inelegant, as per me.

I request an alternate proof (or its source), & have found only one other post on topic on MSE. That post did not address the uniqueness aspect also, although was non-inductive.

Answer 1

• Notice that $g^m$ is increasing and unbounded, hence given any positive number $a$, we will be able to find a unique $n$ such that $g^n \le a < g^{n+1} $. Another way to understand this is note that $\{[g^i, \ldots, g^{i+1})\cap \mathbb{Z}: i \in \mathbb{Z}^+ \}$ is a partition of the positive integers and $a$ must be inside one of them.

• The induction hypothesis is $\forall v \in \mathbb{Z}, 1 \le v <a, $ then we can write $v$ in the form of $\sum_{i=0}^mb_i g^i$, where $0 \le b_i < g, b_m>0$. So before I use the induction hypothesis on a particular integer $v$, I will check whether it satisfies $1 \le v < a$. If it does, then I can write it in that form.

• Now, we are given $a$, we find the interval that I mentioned in the first pointer that it resides, that is find $n$ such that $g^n \le a < g^{n+1}$. Since $g^n \le a$, we can use division algorithm to write $$a=c_ng^n+r$$

$$c_n \ge 0, 0 \le r < g^n$$

• Suppose $c_n =0$, then $r=a<g^n \le a$ which is a contradiction, hence $c_n >0$.

• If $r=0$, $a=c_ng^n$, problem solved, just set the remaining term to zero.

• If $r>0$, then we have $1 \le r < g^n \le a $, that is it satisfies the indunction hypothesis, hence we can write $r=\sum_{i=0}^t b_ig^i$ where $b_t \neq 0$. Hence overall, $a=c_ng^n +\sum_{i=0}^t b_ig^i $.

• Now onto the proof of uniqueness, first check that $1$ can be written uniquely. If any coefficient of $g^i$ where $i>0$ is posisitive, that the term is greater than $1$. Hence $1$ can be written uniquely.

• We focus on $a>1$.

suppose $$a=\sum_{i=0}^nc_ig^i, \text{where } c_n >0$$ and $$a=\sum_{i=0}^md_ig^i , \text{where } d_m >0.$$

Suppose those two expression are different and we assume $n \le m$, there must be a smallest index $j$ such that $c_j \neq d_j$.

• Suppose $j > n$, then we have $$a=\sum_{i=0}^{n} c_ig^i+\sum_{i={n+1}}^md_ig^i=a+\sum_{i={n+1}}^md_ig^i$$

Hence $$\sum_{i={n+1}}^md_ig^i=0 \ge d_mg^m>0$$ which is a contradiction.

• Now suppose $j \le n$,

  $$a-\sum_{i=0}^{j-1}c_ig^i =\sum_{i=j}^nc_ig^i, \text{where } c_n >0$$ and $$a-\sum_{i=0}^{j-1}c_ig^i=\sum_{i=j}^md_ig^i , \text{where } d_m >0.$$

Divide both equations by $g^j$,

$$g^{-j}\left(a-\sum_{i=0}^{j-1}c_ig^i\right) =c_j+\sum_{i=j+1}^nc_ig^{i-j}, \text{where } c_n >0$$ and $$g^{-j}\left(a-\sum_{i=0}^{j-1}c_ig^i\right)=d_j+ \sum_{i=j+1}^md_ig^{i-j} , \text{where } d_m >0.$$

If you divide both expression by $g$, we can see that one gives remainder $c_j$ and one gives remainder $d_j$, violating the uniqueness of remainder.

Answer 2

Here is a sketch of an alternative proof.

Let $\beta \ge 2$ and define $D \subset \Bbb N$ by writing

$\quad D = \{0,1\} \text{ when } \beta = 2 \quad \text{else } D = \{0,1,\dots,\beta-1\}$

Let the integer $a$ have a $\text{base-}\beta$ representation,

$\tag 1 \displaystyle \large a = \sum_{k = 0}^{+\infty} a_k \, \beta^{k} \quad \text{where } a_k \in D$

Let $j \ge 0$ and write as true

$\quad a_j + 1 = r \text{ where } 0 \le r \lt \beta \quad \text{XOR} \quad a_j + 1 = \beta + s \text{ where } 0 \le s \lt \beta$

Define the subscripted family $\large ({a'}_k)_{k \ge 0}$

$\quad {a'}_j = r \; \text{ XOR } \; {a'}_j = s \quad \text{AND} \quad {a'}_k = a_k \text{ when } k \ne j$

It is elementary to write as true

$\quad \displaystyle \large \beta^j + a = \sum_{k = 0}^{+\infty} {a'}_k \, \beta^{k} \; \text{ (the term is 'absorbed')}\quad \text{ XOR } \quad \beta^j + a = \beta^{j+1} + \sum_{k = 0}^{+\infty} {a'}_k \, \beta^{k} \; \text{ (we have to 'carry' the $1$ to the next exponent)}$

Since the integer $\large \beta^j + a$ is bounded above, we conclude that it must also have a representation
(eventually the '$\beta \text{ to a power}$' term can be 'folded' into the representation).

Since any $\text{base-}\beta$ representation can be expressed as a sum of these primitive $\beta^j$ terms,
we've demonstrated the following result.

Proposition 1: The sum of any two $\text{base-}\beta$ representations also has a representation.

Using proposition 1,

Proposition 2: There exist a $\text{base-}\beta$ representations for every natural number.
Proof
This is immediate since any submonoid of $(\Bbb N,+)$ containing $1$ contains all the natural numbers. $\quad \blacksquare$

If $a$ satisfies $a_k = 0$ for $k \ge j$ then it is not difficult to show that

$\quad a \lt \beta^j$

Using this fact and a proof by infinite descent, one also get the uniqueness.

Proposition 3: Any two $\text{base-}\beta$ representations of a natural number are identical.