Show that every nonzero integer has balanced ternary expansion? [closed]

Method 1:

It is easy to show that every non-zero Integer can be represented uniquely in base $3$. In base $3$ representation of each number, replace $2.3^k$ with $3^{k+1}-3^k$ until there are only $-1,0,1$ as coefficients of powers of $3$.

You arrive at the ternary representation of the Integer.

Method 2:

This can also be proved by Induction as follows:

It is enough to prove that every non-zero Integer has a unique ternary expansion in the range $[3^j,3^{j+1}]$ where $j \ge0$

Basis: Clearly, the statement holds for $j=0$

$1 = 3^0$, $2 = 3^1-3^0$, $3 = 3^1$

Induction: To show that if the statement is true until some integer $k-1$, then it true for $k$.

Consider the range $[3^k,3^{k+1}]$. Since, it is true until $k-1 \implies$ Every Integer in the range $[1, 3^k]$ has a unique ternary representation. For each representation in this range, add $3^k$. We get a unique representation for the integers in the range $[3^k+1, 2.3^k]$.

Now, consider adding $3^{k+1}-3^k = 2.3^k$ to each integer representation in the range $[1,3^k]$. We have a unique representation for integers in the range $[2.3^k+1,3^{k+1}]$.

Combining both, we have a unique representation for integers in the range $[3^k,3^{k+1}] \implies$ The statement is true for the integer $k$.

Hence Proved.

Proof by Strong Induction.

Let $P(n) : n = 3^m + 3^{m-1}b_{m-1} + \cdots + 3^0b^0 \text{ where each b = -1, 0 or 1 }$.

Base Case: P(1) is true. Since $1 = 3^0$.

Assuming $P(1), P(2), \cdots, P(n-1)$ is true to prove it for $n$.

Considering cases:

Case 1: $n = 3m$ $$\implies n = 3(3^m + 3^{m-1}b_{m-1} + \cdots + 3^0b_0)$$ $$\implies n = 3^{m+1} + 3^{m}b_{m-1} + \cdots + 3^1b_0 + 3^0*0$$

Case 2: $n = 3m+1$ $$\implies n = 3(3^m + 3^{m-1}b_{m-1} + \cdots + 3^0b_0) + 1$$ $$\implies n = 3^{m+1} + 3^{m}b_{m-1} + \cdots + 3^1b_0 + 3^0*1$$

Case 3: $n = 3m-1$ $$\implies n = 3(3^m + 3^{m-1}b_{m-1} + \cdots + 3^0b_0) - 1$$ $$\implies n = 3^{m+1} + 3^{m}b_{m-1} + \cdots + 3^1b_0 + 3^0*(-1)$$

So we find that any number can be expressed like a balanced ternary expansion.