0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The answer math.stackexchange.com/a/607774/139123 addresses uniqueness in any base, though it invokes induction. $\endgroup$ – David K Mar 6 '18 at 5:20
  • 1
    $\begingroup$ It's unclear what you're asking about the inductive proof. That proof is phrased as strong induction, not weak induction. $\endgroup$ – David K Mar 6 '18 at 5:23
  • $\begingroup$ @DavidK Thanks for providing link to another post on MSE, but that is even smaller, more informal proof. Please help on this one, as there is much less work needed on this, if take the inductive proof. Thanks, for stating that it is a strong induction based one. I am unable to understand even that part then. Please elaborate more by an answer, if possible. To make myself more clear, I am unclear about how the proof proceeds, as shown by my inability to understand the type of induction used. Even informal explanation in a few lines may help me. $\endgroup$ – jiten Mar 6 '18 at 5:24
  • 1
    $\begingroup$ "I feel that the inductive proof is unclear on how it has used the second step" And why do you feel that? What was unclear about it. $\endgroup$ – fleablood Mar 6 '18 at 5:44
  • $\begingroup$ @fleablood The proof assumes the second step for any integer < a. It also states for specific powers $n, n+1$ of $g$, for which $a$ is exactly bounded. But, the next step, is not visible to me even. $\endgroup$ – jiten Mar 6 '18 at 6:06
1
$\begingroup$
  • 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.

$\endgroup$
  • $\begingroup$ Thanks for providing an elegant proof for uniqueness part. However, I might be really stupid as still am not able to see (for the main (first part)) the third step of the strong induction being applied, or even how strong induction is being used. $\endgroup$ – jiten Mar 6 '18 at 9:15
  • 1
    $\begingroup$ Strong induction allows us to write $r$ in that particular form and the reason why we can do that is because $1 \le r < a$. That is we assume the statement is true for every positive integer less than $a$. In contrast to weak induction, weak induction only assume the statement is true for integer $a-1$, $\endgroup$ – Siong Thye Goh Mar 6 '18 at 9:24
  • $\begingroup$ But, then the whole proof is an informal one - in my sense as no formula is derived or proved. It is at best a formal version of an informal proof based on inductive approach. $\endgroup$ – jiten Mar 6 '18 at 9:33
  • 1
    $\begingroup$ huh, you have proven that $\forall g \in \mathbb{Z}^+, \forall a \in \mathbb{Z}^+, $ there exists a unique $n \ge 0$ , such that $a= \sum_{i=0}^n c_ig^i, c_n>0, 0 \le c_i < g$. Existence and uniqueness proof is quite common in maths. $\endgroup$ – Siong Thye Goh Mar 6 '18 at 14:54
  • $\begingroup$ I have read some answer at math.stackexchange.com/a/2408201/424260, and am pretty confused over the first line of it. I even made a post on it, as could not raise a direct question, and my post, and in particular comments to an answer are at: math.stackexchange.com/a/2681897/424260. I request you to comment either at the original answer at: math.stackexchange.com/a/2408201/424260 (preferably), or at my post. $\endgroup$ – jiten Mar 8 '18 at 5:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.