Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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\}$.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer

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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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