# In the proof for the Basis Representation Theorem, how does the range of the coefficients fit into the picture?

To my understanding, the Basis Representation Theorem says that for any integer base $b > 1$, any integer $n > 0$ can be written as:

$$n = \sum_{k=0}^{s} c_kb^k$$

where $c_k \in \{0,1,...,b-1\}$.

In this proof of the Basis Representation Theorem, how does the statement that $c_k \in \{0,1,...,b-1\}$ fit into the picture?

I ask because I am trying to prove that, for the case of $b = 3$, $n$ can be written as either:

$$n = \sum_{k=0}^{s} c_k3^k$$

where $c_k \in \{0,1,2\}$, or

$$n = \sum_{k=0}^{s} d_k3^k$$

where $d_k \in \{-1,0,1\}$.

-

The limitation of the coefficients to the set $\{0,1,\dots,b-1\}$ is used when it’s shown that if $$n=r_kb^k+r_{k-1}b^{k-1}+\ldots+r_tb^t$$ with $r_k\ne 0\ne r_t$, then

$$n-1=r_kb^k+r_{k-1}b^{k-1}+\ldots+(r_t-1)b^t+\sum_{j=0}^{t-1}(b-1)b^j\;:$$

this wouldn’t be a valid representation of $n-1$ if $b-1$ were not in the set of possible coefficients.

For the balanced ternary system with coefficients in $\{-1,0,1\}$ I’d be inclined to start from scratch rather than to try to deduce a representation theorem from the usual one. Start with uniqueness. Suppose that $n\in\Bbb Z$ has two balanced ternary representations, say

$$n=\sum_{k=0}^rc_k3^k=\sum_{k=0}^sd_k3^k\;,$$

where $r\le s$ and all $c_k,d_k\in\{-1,0,1\}$; then if we let $c_k=0$ for $r<k\le s$ we can write

$$\sum_{k=0}^s(d_k-c_k)3^k=0\;.$$

The coefficients $d_k-c_k$ are all in the set $\{-2,-1,0,1,2\}$.

Lemma. If $a_k\in\{-2,-1,0,1,2\}$ for $k=0,\dots,t$ and $a_t\ne0$, then $\sum_{k=0}^ta_k3^k\ne0$.

Proof. Without loss of generality assume that $a_t>0$. (Otherwise just multiply everything by $-1$.) Then $$\sum_{k=0}^ta_k3^k\ge 3^t-2\sum_{k=0}^{t-1}3^k=3^t-2\frac{3^t-1}{3-1}=3^t-\left(3^t-1\right)=1\;.\qquad\qquad\dashv$$

It follows from the lemma that the coefficients $d_k-c_k$ are all $0$ and hence that the two representations of $n$ are identical.

To show that each $n\in\Bbb Z$ has at least one balanced ternary representation, it suffices to show that each positive integer has one: clearly if $n=\sum_{k=0}^rc_k3^k$, then $-n=\sum_{k=0}^r(-c_k)3^k$. Suppose, then, that there is at least one positive integer with no balanced ternary representation, and let $n$ be the smallest such integer. Clearly $n>1$, so by hypothesis there are a non-negative integer $r$ and $c_k\in\{-1,0,1\}$ for $k=0,\dots,r$ such that $n-1=\sum_{k=0}^rc_k3^k$. If $c_0\ne 1$, $$n=(c_0+1)+\sum_{k=1}^rc_k3^k$$ is a valid representation of $n$, so we must have $c_0=1$. If some $c_k\ne 1$, let $s$ be minimal such that $c_s\ne1$. Then

\begin{align*} n&=\sum_{k=s+1}^rc_k3^k+c_s3^s+\sum_{k=0}^{s-1}3^k+1\\ &=\sum_{k=s+1}^rc_k3^k+c_s3^s+\frac{3^s-1}{3-1}+1\\ &=\sum_{k=s+1}^rc_k3^k+c_s3^s+\frac{3^s+1}2\\ &=\sum_{k=s+1}^rc_k3^k+c_s3^s+\left(3^s-\frac{3^s-1}2\right)\\ &=\sum_{k=s+1}^rc_k3^k+c_s3^s+(c_s+1)3^s-\sum_{k=0}^{s-1}3^k\;. \end{align*}

Now $c_s\ne 1$, so $c_s+1\in\{-1,0,1\}$, Thus, if we let $d_k=-1$ for $k=0,\dots,s-1$, $d_s=c_s+1$, and $d_k=c_k$ for $k=s+1,\dots,r$, $$n=\sum_{k=0}^rd_k3^k$$ is a valid balanced ternary representation of $n$. This contradiction shows that every positive integer has a balanced ternary representation and hence that every integer has one.

-

Well, the $-1$ as digit is not usual. Thus, you would like to see $5$ as with digits '1(-1)(-1)' (meaning $9-3-1$)?

Anyway, it seems that with your $d_k$ every integer can be uniquely written.

-
The system with digits $-1,0,1$ is known as balanced ternary. – Brian M. Scott Oct 30 '12 at 19:11