prove that $2^{n}+1$ is divisible by $n=3^k$ for $k≥1$

Question

prove that :

$2^n+1$ is divisible by all number from : $n=3^k$

for $k≥1$

I find this problems in book and I need ideas to approach it

Problems :

Answer 1

Approach by induction. We first check that it is true for $k=1$. Indeed, $2^{(3^1)}+1=9$ is divisible by $3^1=3$

Rewording the claim, $3^k \mid 2^{(3^k)} + 1$. Reworded again, there exists some $a$ such that $2^{(3^k)}+1 = 3^k\cdot a$

Suppose that the claim is true for some $k\geq 1$. We try to show that it is also true for $k+1$.

$2^{(3^{k+1})}+1 = 2^{3(3^k)}+1 = (2^{(3^k)})^3+1 = (3^k\cdot a - 1)^3+1$

$=(3^k)^3\cdot a^3-3\cdot (3^k)^2\cdot a^2+3\cdot 3^k\cdot a - 1 + 1$

Now, from here, it should be clear that after cancelling the $-1$ and the $+1$ that each term is divisible by $3\cdot 3^k$ and the claim is proven.