How to prove by induction that $3^{3n}+1$ is divisible by $3^n+1$ for $(n=1,2,...)$

As an interesting alternative, note that $x^3 +1 = (x+1)(x^2 - x + 1)$, so setting $x = 3^n$ gives $3^{3n} + 1 = (3^n + 1)(3^{2n} - 3^n + 1)$.

It's true for $n=1$. Assume it holds for $n$, i.e: $3^{3n} + 1 = k(3^n +1)$ then consider $$3^{3(n+1)} +1 = 27 \cdot 3^{3n} + 1 = 27 (3^{3n} +1) - 26 = 27k(3^n +1) - 26$$

Let's get it into a more amenable form $$\begin{equation}3^{3(n+1)} +1 = 9k3^{n+1} + 27k - 26 = 9k(3^{n+1}+1) + 18k - 26 \end{equation} \tag{1}$$

So we want to show that $3^{n+1} + 1$ always divides $18k - 26$ where $$k = \frac{3^{3n} + 1}{3^n + 1} = 3^{2n} - 3^n + 1$$

Equivalently we want to show that $3^{n+1} + 1$ divides $18\cdot 3^{2n} - 18 \cdot 3^n - 8 $. But: $$18\cdot 3^{2n} - 18 \cdot 3^n - 8 = 2(3^{n+1} - 4)(3^{n+1} + 1) \quad \quad (\star)$$

It is then clear that $3^{n+1} + 1$ divides $18k - 26$ since $2(3^{n+1} - 4)$ is an integer.

And hence, since $3^{3(n+1)} + 1$ is the sum of two terms (see $(1)$), each divisible by $3^{n+1} + 1$, where the divisibility holds due to a relation we exploited from the inductive hypothesis, we are done inductively.

---

If $(\star)$ seems a bit magical, simply look at $f(x) = 18x^2 - 18x - 8 = 2(3x-4)(3x+1)$ and substitute in $x = 3^n$.