Uniqueness of radix representation of integers in base 3

Solution 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.

Solution 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.

Solution 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$$