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.

We  show, as was observed by Sivaram Ambikasaran, that $3^{n+1}$ divides $2^{3^n}+1$.  For $\varphi(3^{n+1})=2\cdot 3^n$.  By Euler's Theorem,  $2^{2\cdot 3^n}\equiv 1\pmod{3^{n+1}}$. Thus $2^{3^n}\equiv \pm 1 \pmod{ 3^{n+1}}$.  But $2^{3^n}\not\equiv 1 \pmod{3}$, so $2^{3^n}\equiv -1\pmod{3^{n+1}}$. 
Remark: It is not hard to show that $2$ is a primitive root of $3^{e}$ for every positive integer $e$. As a consequence, $2^{3^n}+1$ is not divisible by any power of $3$ greater than $3^{n+1}$.
