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

Question

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.

Answer 1

I agree with you that induction is unnecessary here. However, if you want to construct this in the form of an induction proof, it follows very similar lines.

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.

It is true that the inductive step relies in no way on any of the previous steps, making induction unnecessary, so I would stick with your method, if possible. I hope this helps!

Answer 2

It seems unnecessary, but one approach might be that if your inductive hypothesis is:

$$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$