Uniqueness of radix representation of integers in base 3

Question

I have recently begun self-studying Number Theory, and am working on proving:

Show that every integer $n>0$ can be uniquely written as $$n = \sum_{i=0}^mc_i3^i$$ where $c_i \in \{ -1,0,1\}$ and $c_m \neq 0$.

I believe I have already shown the existence portion of this proof correctly, and now I am looking for some hints on the uniqueness part. So far what I have tried is:

Suppose for the sake of contradiction that there is an alternate representation of $n$ besides $n = \sum_{i=0}^mc_i3^i$, say $n = \sum_{i=0}^pb_i3^i$ where we still have $b_p \neq 0$ and $b_i \in \{-1,0,1\}$.

At this point I felt that I first need to establish that $m=p$, and second show $c_i=b_i$ for each $i \in \{1,2,\dots, m\}$. To show the former, I left off in my proof by contradiction with

Without loss of generality suppose $p>m$. We know there is an integer $q$ such that $m+q=p$. We have two ways of writing $n$, which means $$ \sum_{i=0}^pb_i3^i-\sum_{i=0}^mc_i3^i=0 \\ \implies \left(\sum_{i=0}^mb_i3^i+\sum_{i=m+1}^{m+q}b_i3^i\right)-\sum_{i=0}^mc_i3^i=0 \\ \implies \sum_{i=0}^m(b_i-c_i)3^i+\sum_{i=m+1}^{m+q}b_i3^i=0 \\ \implies \sum_{i=m+1}^{m+q}b_i3^i=\sum_{i=0}^m(c_i-b_i)3^i$$

At this point I am stuck. If anyone has any hints to help me find the contradiction or feel that there is a better way to establish uniqueness, please let me know!

Answer 1

If you know a bit about modular arithmetic, then there is a relatively easy way to work this out (it is equivalent to the proofs already here, but perhaps is a little cleaner conceptually). Suppose that you have $x_0 = \sum_{n = 0}^\infty a_n 3^n = \sum_{n = 0}^\infty b_n 3^n$ (with the understanding that for large enough $n$, $a_n$ and $b_n$ are $0$).

Take $x_0$ modulo $3$. It is apparent that we must have $x_0 = a_0 = b_0 \mod 3$, which of course implies that $a_0 = b_0$. Now, consider $x_1:=\frac{x_0 - a_0}{3}$. It is an integer, so it makes sense to reduce it modulo $3$ again---this time, we get the equality $x_1 = a_1 = b_1 \mod 3$, so $a_1 = b_1$. Define $x_2 := \frac{x_1 - a_1}{3}$, rinse, and repeat. An easy induction proves the result.

Answer 2

The best approach is to use induction.

If $\sum a_i3^i = \sum b_i3^i$, first show that $a_0=b_0$ and thus that:$$\sum_{i>0} a_i3^{i-1} = \sum_{i>0} b_i3^{i-1}$$ Then apply the induction hypothesis.

Answer 3

Hint $\ $ Viewing radix representation as a polynomial in the radix, this can be reduced to a result related to the rational root test - see the result below, which, slightly modified, also works here.

---

If $\,g(x) = \sum g_i x^i$ is a polynomial with integer coefficients $\,g_i\,$ such that $\,0\le g_i < b\,$ and $\,g(b) = n\,$ then we call $\,(g,b)\,$ the radix $\,b\,$ representation of $\,n.\,$ It is unique: $ $ if $\,n\,$ has another rep $\,(h,b),\,$ with $\,g(x) \ne h(x),\,$ then $\,f(x)= g(x)-h(x)\ne 0\,$ has root $\,b\,$ but all coefficients $\,\color{#c00}{|f_i| < b},\,$ contra the following slight generalization of: $ $ integer roots of integer polynomials divide their constant term.

Theorem $\ $ If $\,f(x) = x^k(\color{#0a0}{f_0}\!+f_1 x +\cdots + f_n x^n)=x^k\bar f(x)\,$ is a polynomial with integer coefficients $\,f_i\,$ and with $\,\color{#0a0}{f_0\ne 0}\,$ then an integer root $\,b\ne 0\,$ satisfies $\,b\mid f_0,\,$ so $\,\color{#c00}{|b| \le |f_0|}$

Proof $\,\ \ 0 = f(b) = b^k \bar f(b)\,\overset{\large b\,\ne\, 0}\Rightarrow\, 0 = \bar f(b),\,$ so, subtracting $\,f_0$ from both sides yields $$-f_0 =\, b\,(f_1\!+f_2 b+\,\cdots+f_n b^{n-1})\, \Rightarrow\,b\mid f_0\, \overset{\large \color{#0a0}{f_0\,\ne\, 0}}\Rightarrow\, |b| \le |f_0|\qquad {\bf QED}\qquad\quad$$

Answer 4

Hint:

• Note that $$(3^m+3^{m-1}+\ldots+1)-(-3^m-3^{m-1}-\ldots-1)=3^{m+1}-1$$ since $3-1=2$ and $3^{m+1}-1=3\cdot3^m-1=2\cdot3^m+(3^m-1)$.
• You could strengthen your argument so that each integer from $(-3^m-\ldots-1)$ to $(3^m+\ldots+1)$ can be expressed.
• In such case you are representing $3^{m+1}$ possibilities with at most $3^{m+1}$ different sums, that is, you get uniqueness for almost free.
• The first bullet makes for an elegant induction hypothesis, because $$3^{m+1}+(-3^m-3^{m-1}-\ldots-1) = (3^m+3^{m-1}+\ldots+1)+1.$$

I hope this helps $\ddot\smile$

Answer 5

Outline of Proof: 1) first assume n has a representation as required

2) Show that for each representation of $n$ we can find a representation for $n-1$. This means if we know a representation for an integer greater than $n$, we can find one for $n$.

3)$3^n$ is greater than n and has a representation; therefore so does $n$

4)Squeeze the number of representations for $n$ between 1 and 1.

Suppose that n has a representation of the form $n = \sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+c_03^0$. Now we want to subtract 1 from both sides, $n-1 = \sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+c_03^0-1$. Now, $n-1$ does not have the proper representation yet. On its own $-1$ can be written $-1=-1*3^0$. We can now write $n-1 = \sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+(c_0-1)3^0$.

We want to say here that given a representation of $n$ satisfying the requirements we can find a representation of $n-1$ that does as well, but for the case $c_0=-1$ we get a coefficient of $-2$ for the last term.

So for the case $c_0=-1$ we will use the formula $-2*3^j=-3^{j+1}+3^j$ to rewrite $n-1$.$n-1 = \sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+(c_0-1)3^0=c_m3^m+c_{m-1}3^{m-1}+...-2*3^0=c_m3^m+c_{m-1}3^{m-1}+...-3^1+3^0$. Now we realize that there may exist a term w/ coefficient $-1$ and exponent $1$ and we are back where we started.

But, there must exist a last term with $-1$ as a coefficient. Let the kth term be the last one with coefficient $-1$, then we have $n-1=c_m3^m+c_{m-1}3^{m-1}+...-3^{k+1}+3^k+3^{k-1}+...+3^0 $ and this representation meets the requirements.

So we have shown that for each representation of $n$ we can find a representation for $n-1 $. Since $3^n>n>0$ and $3^n$ has a representation(itself) then a representation for n can be found progressively.

Uniqueness:

Let $b_k(n)$ represent the total number of representations for $n$. Since for each representation of $n$ we can find one for $n-1$ we have $b_k(n)$<=$b_k(n-1)$. (Skipping a bit) we have finally 1<=$b_k(3^n)<=b_k(n)<=b_k(1)=1$. The total number of representations for $n$ is between $1$ and $1$ and must therefore be $1$