# Induction proving for $3^{n}+1 | 3^{3n}+1$

I find myself in difficult situation, it stays that I need to prove this $3^{n}+1 | 3^{3n}+1$ by induction and I don't know how to. It is trivially to calculate, that for every $n$ $$\frac{3^{3n}+1}{3^n+1}=9^n-3^n+1.$$ But it's not an induction prove.

Base for induction is also trivial and easy, then assume that it states for $n=k$ and prove for $k+1$. If it states for k, then $3^{3k}+1=m(3^k+1)$ So, I try writing $3^{3k}$ as $m\cdot(3^k+1)-1$ in last step, but it is not helping. And I don't a thing that can help here.

The base case is easy, as you say. Now suppose that the result holds for $k$. Then for $k + 1$, we wish to prove that $$3^{k+1} + 1 \mid 3^{3(k+1)} + 1$$ Using the identity $$x^3 + y^3 = (x + y)(x^2 - xy + y^2)$$ We can write $$3^{3(k+1)} + 1 = (3^{k+1} + 1)(3^{2(k+1)} - 3^{k+1} + 1)$$ Therefore, we see that $3^{k+1} + 1 \mid 3^{3(k+1)} + 1$, as desired, proving our inductive step and our result.
$$3^{3n}+1 = (3^n+1)(9^n-3^n+1)$$ and this is true for $n=k$ then multiplying both sides by $27$ gives $$3^{3(k+1)}+27 = (3^{k+1}+3)(9^{k+1}-3\times 3^{k+1}+9)$$ so reorganising and multiplying out and then tidying up $$3^{3(k+1)}+1 = (3^{k+1}+1+2)(9^{k+1}- 3^{k+1}+1+8-2\times 3^{k+1}) - 26$$ $$= (3^{k+1}+1)(9^{k+1}- 3^{k+1}+1)$$ so showing the inductive hypothesis applies for $n=k+1$