0

If I assume, by strong induction, that for all elements less than $n+1$, there exists a representation of $n$ as distinct powers of $3$, i.e $73=3^0-3^2+3^4$ and $81=3^4$, $328=3^0+3^1+3^4+3^5$, and I Want to show that it holds for $n+1$, then I considered the three representations of numbers $3k$, $3k+1$ and $3k+2$. I didn't have a problem proving the first $2$ using strong induction, but the $n+1=3k+2$ case where I assume it holds for all $n<n+1$ is where I am stuck.

Bill Dubuque
  • 272,048
john fowles
  • 2,475
  • Maybe write $3k + 2 = 3(k+1) - 3^0$? All the terms in $3(k+1)$ would be of the form $3^r$ for $r \geq 1$ so you can definitely subtract a $3^0$ and avoid repetition. – sudeep5221 Oct 10 '20 at 02:20

1 Answers1

1

If $n+1 = 3k+2$, then $n+1 = (3k+3) - 1 = 3(k+1) - 1$, where $k+1 \leq n$. So take a decomposition for $k+1$ in terms of sums/differences of powers of $3$; multiply it by $3$; and then subtract $1$. Voila, you have the desired decomposition of $3k + 2$.

Example: Suppose we know it's true up to $n = 16$, and we want to prove it's true when $n = 17 = 3(5)+2$.

We start by writing $17 = (18 - 1) = 3(6) - 1$.

By hypothesis, $6$ had such a decomposition: explicitly, $6 = 9 - 3 = 3^2 - 3^1$.

So our decomposition for $17$ is given by

\begin{align*} 17 & = 3(6) - 1 \\ &= 3(3^2 - 3^1) - 1 \\ &= 3^3 - 3^2 - 1 \\ &= 3^3 - 3^2 - 3^0, \ \end{align*}

which is of the desired form.

Rivers McForge
  • 5,787