<s>[INST] Show that $2^{3^k}+1$ is divisible by $3^k$ for all positive integers $k$ I attempted this by induction: Here is what I did
For $k=1, 2^{3^{1}}+1 = 2^{3}+1 = 9 = 3^{2}$ is divisible by $3^{1}$ , so the result is true for $k=1$
Now I assume the result to be true for $k=m$, 
$2^{3^{m}}+1$ is divisible by $3^m$. To show the result to be true for $k=(m+1)$,
$2^{3^{m+1}}+1 = 2^{3^m} \times 2^3+1$ and I was stuck here.
 [/INST] The last step you did can be corrected as
$$2^{3^{m+1}}+1 = (2^{3^m})^3+1$$ because if you look at it this way
$$(2^{3^m})^3 = (2^{3^m}) \times (2^{3^m}) \times (2^{3^m}) = 2^{3 \times 3^m} = 2^{3^{m+1}}$$   
Using the fact that the result is true for $k=m$
$$2^{3^{m}}+1 = x \times 3^{m} \implies 2^{3^{m}} = x3^{m}-1 \tag{B}$$
$$
\begin{align*}
2^{3^{m+1}} &= (2^{3^m})^3 \\
&= (x3^{m}-1)^3  \\
&= x^3 3^{3m}-x^2 3^{2m+1}+x3^{m+1}-1\\
\end{align*}
$$
Which means 
$$2^{3^{m+1}}+1 = x^3 3^{3m}-x^2 3^{2m+1}+x3^{m+1} \tag{A}$$
And clearly $(A)$ shows the right side is divisible by $3^{m+1}$ because each term is divisible by $3^{m+1}$
which means $2^{3^{m + 1}}+1 = y3^{m+1}$ for some $y$, or the result is true for $k=(m+1)$.
</s>