prove that ${3^{3n}} + 3^{2n} + 3^{n } + 1$ is divided by $4$. by induction

Question

I tried to take the 3 out but it is not helping me much.

Answer 1

We have $$ 3^0 \equiv +1 \bmod 4 \\ 3^1 \equiv -1 \bmod 4 \\ 3^2 \equiv +1 \bmod 4 \\ 3^3 \equiv -1 \bmod 4 \\ $$ Therefore, $3^{3n}+3^{2n}+3^{n} + 1 \equiv 1^n +(-1)^n + 1^n + (-1)^n \equiv 0 \bmod 4$.

Answer 2

Let $a_n=3^{3n}+3^{2n}+3^{n} + 1 = (3^3)^n+(3^2)^n+(3^1)^n + (3^0)^n$. Since $$(x-3^3)(x-3^2)(x-3^1)(x-3^0)= x^4 - 40 x^3 + 390 x^2 - 1080 x + 729$$ we have $$ a_{n+4} =40 a_{n+3} - 390 a_{n+2} + 1080 a_{n+1} - 729a_{n} $$ The claim that $a_n$ is a multiple of $4$ for all $n$ follows by induction since it is true for $n=0,1,2,3$.

(The actual coefficients in that recurrence do not matter. It only matters that they are integers.)

Answer 3

$$...= 3^{2n}(3^n+1)+(3^n+1)= (3^{2n}+1)(3^n+1)$$

Notice that $(3^{2n}+1)$ and $(3^n+1)$ are even, so you are done.

Answer 4

You are on the right track. The proposition that you want to prove using induction is $$P(n): 4\mid \underbrace{3^{3n}+3^{2n}+3^n +1}_{:=a_n}$$ It is easy to check that $P(0)$ holds. Assume that $P(n)$ holds for some integer $n\ge 0$ (that is, $a_n$ is a multiple of $4$) and consider $$a_{n+1}=27\cdot 3^{3n}+9\cdot 3^{2n}+3\cdot 3^n+1=3a_n+24\cdot 3^n +6 \cdot3^{2n}-2.$$
Notice that $3a_n$ and $24\cdot 3^n$ are clearly multiples of $4$. Also $$6 \cdot3^{2n}-2 = 2\underbrace{(3^{2n}-1)}_{\text{even}} $$ is a multiple of $4$. Therefore, $a_{n+1}$ is a multiple of $4$.

Answer 5

By induction?

Well if we assume $3^{3n} + 3^{2n} + 3^n + 1= 4K$ then

$3^{3(n+1)} +3^{2(n+1)} + 3^{n+1} + 1=$

$3^{3n+3} + 3^{2n + 2} + 3^{n+1} + 1=$

$3^{3n}*27 + 3^{2n}*9 + 3^n*3 + 1 =$

$[3^{3n} + 3^{2n} + 3^n+1] + 26*3^{3n} + 8*3^{2n} + 2*3^n =$

$4K + 4(6*3^{2n} + 2*3^{2n}) + 2(3^{3n} + 3^n) =$

$4[K+(6*3^{2n} + 2*3^{2n})] + 2*3^{n}(3^{2n} + 1)=$

$4[K+(6*3^{2n} + 2*3^{2n})] + 4*3^{n}*\frac {3^{2n} + 1}2$.

The only thing left to prove is that $3^{2n} + 1$ is even and.... c'mon.....!

Answer 6

Hint:

Your expression is a geometric series $$\frac{3^{4n}-1}{3-1}$$

You also have that $$3^{4n}=(4-1)^{4n}=\sum_{i=0}^{4n}\binom{4n}{i}4^i(-1)^{4n-i}$$