Theorem: Existence and Uniqueness of Balanced Ternary Integer Representations
Given any positive integer \(n\), \(n\) has a unique representation in the form
$$n= d_{r}\cdot 3^{r}+d_{r-1}\cdot 3^{r-1}+...+d_{2}\cdot 3^{2}+d_{1}\cdot 3+d_{0}$$
Where \(r\) is a nonnegative integer, \(d_{r}=1\), and \(d_{j}=-1,0,1\) for all \(j=0,1,2,...,r-1\).
Proof:
We provide separate proofs to demonstrate both the existence and the uniqueness of the balanced ternary representation.
Existence (proof by strong mathematical induction): Let \(P(n)\) be the equation $$n= d_{r}\cdot 3^{r}+d_{r-1}\cdot 3^{r-1}+...+d_{2}\cdot 3^{2}+d_{1}\cdot 3+d_{0}$$ Where \(r\) is a nonnegative integer, \(d_{r}=1\), and \(d_{j}=-1,0,1\) for all \(j=0,1,2,...,r-1\).
Basis step; \(P(1)\) is true:
Let \(r=0\) and \(d_{0}=1\). Then \(1=d_{r}\cdot 3^{r}\), and so \(n=1\) can be written in the required form.
Inductive step; for all integers \(k\ge1\), if \(P(i)\) is true for all integers \(i\) from 1 through k, then \(P(k+1)\) is also true:
Let \(k\) be an integer with \(k\ge 1\). Suppose that for all integers \(i\) from \(1\) through \(k\),
$$i= d_{r}\cdot 3^{r}+d_{r-1}\cdot 3^{r-1}+...+d_{2}\cdot 3^{2}+d_{1}\cdot 3+d_{0}$$
Where \(r\) is a nonnegative integer, \(d_{r}= 1\), and \(d_{j}=-1,0,1\) for all \(j=0,1,2,...,r-1\).
By the quotient-remainder theorem, \(k+1\) can be written in one of the unique forms $$3q \:\:\: \text{or}\:\: 3q+1 \:\: \text{or} \:\: 3q+2$$
for some integer \(q\). Consequently, we divide into cases accordingly
Case 1 (\(k+1=3q\) for some integer \(q\)):
In this case \(\frac{k+1}{3}\) is an integer, and by inductive hypothesis, since \(1\le \frac{k+1}{3} \le k\), then
$$ \frac{k+1}{3} =d_{r}\cdot 3^{r}+d_{r-1}\cdot 3^{r-1}+...+d_{2}\cdot 3^{2}+d_{1}\cdot 3+d_{0}$$
Where \(r\) is a nonnegative integer, \(d_{r}=1\), and \(d_{j}=-1,0,1\) for all \(j=0,1,2,...,r-1\). Multiplying both sides of the equation by \(3\) gives
$$k+1=d_{r}\cdot 3^{r+1}+d_{r-1}\cdot 3^{r}+...+d_{2}\cdot 3^{3}+d_{1}\cdot 3^{2}+d_{0}\cdot 3$$
In this case \(\frac{k}{3}\) is an integer, and by inductive hypothesis, since \(1\le \frac{k}{3} \le k\), then
$$ \frac{k}{3} =d_{r}\cdot 3^{r}+d_{r-1}\cdot 3^{r-1}+...+d_{2}\cdot 3^{2}+d_{1}\cdot 3+d_{0}$$
Where \(r\) is a nonnegative integer, \(d_{r}= 1\), and \(d_{j}=-1,0,1\) for all \(j=0,1,2,...,r-1\). Multiplying both sides of the equation by \(3\) and adding \(1\) to both sides gives
$$k+1=d_{r}\cdot 3^{r+1}+d_{r-1}\cdot 3^{r}+...+d_{2}\cdot 3^{3}+d_{1}\cdot 3^{2}+d_{0}\cdot 3+1$$
In this case, note that \(k+1=3q+3-1=3(q+1)-1\). Let \(s=q+1\), and by the inductive hypothesis, since \(1\le s \le k\),
$$k+1=3s-1$$ $$=3(d_{r}\cdot 3^{r}+d_{r-1}\cdot 3^{r-1}+...+d_{2}\cdot 3^{2}+d_{1}\cdot 3+d_{0})-1$$ $$=d_{r}\cdot 3^{r+1}+d_{r-1}\cdot 3^{r}+...+d_{2}\cdot 3^{3}+d_{1}\cdot 3^{2}+d_{0}\cdot 3-1$$
Where \(r\) is a nonnegative integer, \(d_{r}=1\), and \(d_{j}=-1,0,1\) for all \(j=0,1,2,...,r-1\), which is also a sum of powers of \(3\) of the required form.
The preceding arguments show that regardless of whether \(k+1\) is \(3q\), \(3q+1\), or \(3q+2\) has a representation of the required form.
Uniqueness (proof by contradiction): Suppose, on the contrary. That is, suppose there is an integer \(n\) with two different representations as a sum of nonnegative integer powers of \(3\). Equating the two representations and cancelling all identical terms gives
$$\sum_{i=0}^{r}c_{i}3^{i}=\sum_{i=0}^{s}d_{i}3^{i}$$
Where \(r\) and \(s\) are nonnegative integers, and each \(c_{i}\) and each \(d_{i}\) equal \(-1\), \(0\), or \(1\) except for \(c_{r}=1\) and \(d_{s}=1\). Without loss of generality, we may assume that \(r\lt s\). Subtracting the two expressions gives:
$$0=\sum_{i=0}^{s}d_{i}3^{i}-\sum_{i=0}^{r}c_{i}3^{i}$$ $$\implies \sum_{i=0}^{s}(d_{i}-c_{i})3^{i}=0$$
Assumes \(c_{i} = 0\) for all \(i > r\). Now let \(e_{i} = d_{i}-c_{i}\) where \(e_{i} \in \{ -2, -1, 0, 1, 2 \}\). We now have a nontrivial sum, and thus by substitution,
$$\sum_{i=0}^{s}e_{i}3^{i}=0 \:\:\text{where}, e_{s} \neq 0$$
Note that \(e_{s} = d_{s}-c_{s}=1-0=1\) . Separating off the highest degree term from the sum gives,
$$\sum_{i=0}^{s-1}e_{i}3^{i}+e_{s}3^{s}=0 $$
Rearraging terms, taking the absolute value of both sides of the equation, and using the fact that for all real numbers \(x\), \(\left| -x \right|=\left| x \right|\) gives, $$\left| \sum_{i=0}^{s-1}e_{i}3^{i} \right|=\left| e_{s}3^{s} \right| \: \text{(1)}$$
But by the definition of absolute value and the formula for the sum of a geometric sequence, $$\left| e_{s} \right|= 1 \: \text{and} \:\left| \sum_{i=0}^{s-1}e_{i}3^{i} \right|\le 2\cdot\sum_{i=0}^{s-1}3^{i} =2\cdot\frac{3^{s}-1}{2}=3^{s}-1 $$
Thus, $$\left| \sum_{i=0}^{s-1}e_{i}3^{i} \right| \le 3^{s}-1\lt 3^{s}=\left| e_{s} \right|3^{s}\implies \left| e_{s} \right|\cdot3^{s}\gt \left| \sum_{i=0}^{s-1}e_{i}3^{i} \right|$$
Which contradicts equation (\(1\)) because \(\left| e_{s}3^{s} \right|=\left| e_{s} \right|3^{s}\) by definition of absolute value. Furthermore, the only way the sum could be zero is if \(e_{s}= 0\), contradicting the choice of \(s\) as the highest degree for which \(e_{s} \neq 0\). Hence, the supposition is false, so any integer \(n\) has only one representation in the balanced ternary system.
For further "playing" with this integer representation, see the problem at the end of this article
Comments
Post a Comment