Proof check of proving altered basis representation theorem.

65 Views Asked by At

I am trying to show that an integer $n$ can be written uniquely as $n = \sum_{j=0}^s c_j3^j$ for $c_j \in \{-1,0,1\}$. I think I've a proof, but it is rather similar to the general proof of the basis representation theorem and wanted to double check. I'd appreciate any help and feedback.

Proof: We prove the result via strong induction on $n$. As our base case, take $n=1$, in which case $s=0$ and $c_0 = 1$. Suppose that for each nonzero integer $b < n$, $b$ can be written uniquely as $$b = \sum_{j=0}^sc_j3^j$$ for $c_j \in \{-1,0,1\}$. We wish to show that there exists a representation for $n$. By Euclid's Division Lemma, any integer $n$ can be written in the form $n= qk + r$ for $0 \le q < n$ and $r < k$. Since $3 = b > 1$, $\lvert q\rvert < \lvert n\rvert$ and therefore there exists a representation of $q$ by our inductive statement, or $$q = \sum_{j=0}^sc_j3^j.$$ Thus, our formula for $n$ becomes $$n = \left(\sum_{j=0}^s c_j3^j\right) 3 + r.$$ This proves we can represent $n$ as a ternary number, but we've yet to show that $c_j = \{-1,0,1\}$. We do so by induction. Take as our base case the case of $n=1$. For our inductive hypothesis, take the above representation to be true up to $n$, and we wish to show it is true for $n+1$. That is, $$n = \sum_{j=0}^sc_j3^j = c_0 + c_13 + c_23^2 + \ldots + c_s3^s, \quad \text{for } c_j \in \{-1,0,1\}.$$ Clearly $n+1 = c_0+1 + c_13 + \ldots + c_s3^s.$ If $c_0 + 1 \neq 2$ then we are done, otherwise we make the substitution $c_0 + 1 = 2 = 3-1$ so this becomes $n+1 = -1 + (c_1+1)3 + \ldots + c_s3^s$. If $c_1 + 1 = 2$ then we repeat the same process above, \textit{ad nauseum}, until all $2'$s have been accounted for in the basis representation. What we are left with is a representation of $n+1$, $$n+1 = c_0' + c_1'3 + c_2'3^2 + \ldots + c_s'3^{s'}$$ where $c_j' \in \{-1,0,1\}$. We show uniqueness by strong induction. Take, as our base case, the case of $n=1$. Suppose that for all integers $m < n$, $m$ has a unique representation. We wish to show that $n$ has a unique representation. Suppose not, that is, suppose we've equivalent representations of $n$ given by $$n = \sum_{j=0}^s c_j3^j = \sum_{j=0}^{s'} c_j'3^j, \quad \text{for } c_j,c_j' \in \{-1,0,1\}\ \forall j.$$ But, $$0 = 3\left( \sum_{j=1}^s c_j 3^{j-1} - \sum_{j=1}^{s'} c_j 3^{j-1}\right) + (c_0 - c_0').$$ By Euclid's Division Lemma, however, we see that this representation is unique, so that $c_0 = c_0'$, as well as equivalence between sums. That is, \begin{equation}\tag{5} \sum_{j=0}^{s-1}c_{j+1}3^j = \sum_{j=0}^{s'-1}3^j. \end{equation} These sums are less than $n$, so by our hypothesis they have unique representations. But then $$n = 3\left(\sum_{j=0}^{s-1} c_{j+1}3^j\right) + c_0.$$ By Euclid's Division Lemma, $3$ and $c_0$ are uniquely determined, so it follows that the sums in $(5)$ are equivalent, and $n$ has a unique representation.