Simple induction. Do I have to use it three times for each value?

Question

I have the following problem, $n = e_{k}3^k + \ldots + e_{1}3 + e_0$.

With $k\geq0$, where $e_i \in \{1,0,-1\}$ for all $i \in \{0, \ldots,k\}$

And I have to prove that every natural can be represented that way, with Simple Induction. Do I have to do simple induction three times, each one for a different $e_i$?

Edit:

I got stuck in all of the paths. This is what I have:

• For $e_i=0$: $P(0)=0$, $P(n)=0$, so $P(n+1)=1$ which is natural. (I don't know if this is right).
• For $e_i=-1$: $P(0)=0$, $P(n)=-3^k-...-3-1$, so: $P(n+1)=-1(3^k+...+3)$. (I think in this case I cannot assume that this number is natural).
• For $e_i=1$: $P(0)=0$, $P(n)=3^k+...+3+1$ so: $P(n+1)=3^k+...+3+1+1$

In summary, I don't know what I am doing. I am new at this.

Answer 1

Hint: Every natural number is either a multiple of $3$ or one more or less than a multiple of $3$. For the induction step, if $x = 3^k e_k + \ldots + e_0$, what are $3x-1$, $3x$ and $3x+1$?

Answer 2

It is easy to see that it holds for $n=1$. Suppose the result holds true for $m\leq n$. So $m=a_k3^k+\ldots +a_13+a_0$, for some $a_i$’s in $\{-1,0,1\}$. Now $$\begin{align} m+1 &= (a_k3^k+a_{k-1}3^{k-1}\cdots + a_13+a_0)+1 \\ &=a_k3^k+(a_{k-1}3^{k-1}\cdots + a_13+a_0+1) \\ &=a_k3^k+(e_{k}’3^{k}\cdots + e_1’3+e_0’) \end{align}$$ Where the last line inside the brackets comes from the fact that the bracketed part is at most $m$ ($a_k$ cannot be negative, else $m+1$ would be). If $e_k’\neq 1$ then we are done; otherwise $(a_k+e_k’)3^k=2\cdot3^k=(3-1)3^k=3^{k+1}-3^k$. In this case $$m+1 = e_{k+1}3^{k+1}+e_k3^k+\cdots + e_13+e_0$$ With $e_{k+1}=1$, $e_k=-1$, and $e_i=e_i’$ for every other $i$.