Proof by induction: $4^{3n} +8$ divisible by $9$

Question

Can anyone help me? Tried several times, but didn't get a solution.

Answer 1

Hint:

(1) Start with the induction base (here $n=0$): $4^{3\cdot 0} + 8 = 1+8 = 9$ which is divisible by $9$.

(2) In the induction step, assume that $4^{3n}+8$ is divisible by $9$ for some $n\geq 0$.

Prove that $4^{3(n+1)}+8$ is divisible by $9$ using that $4^{3n}+8$ is divisible by $9$. Just fill in the details.

Answer 2

The base case should be clear. For the induction step write $4^{3(n+1)}+8$ in the form

$$4^{3(n+1)}+8=(4^{3n}+8) \cdot 4^3+8(1-4^3)$$

and show that both summands on the RHS are divisible by $9$.

Answer 3

It is easy to see that equation is true for $P(1)$

Let us assume it is true for $P(n).$

$$ P(n)\implies 9|4^{3n}+8$$ $$ \implies 4^{3n} = 9\lambda - 8 $$ for some value of $\lambda.$

for $P(n+1)$ , we have: $$P(n+1) = 4^{3(n+1)} + 8$$ $$ =4^{3n}.4^3 + 8 $$ $$ = 8(4^{3n}.8 + 1) $$ $$ =8(72\lambda - 64+1) $$ $$=9(64\lambda -56)$$ which is clearly divisible by $9$.

Answer 4

Hint:

If a term is $m=9n$, the next is $$4^3(9n-8)+8=64\cdot9n-56\cdot9.$$

Answer 5

The solution here may become clearer if you notice that

$4^{3n} = (4^3)^n = 64^n$

and

$9|m+8 \iff m \equiv 1 \mod 9$

So you are asked to prove by induction that

$64^n \equiv 1 \mod 9 \quad \forall n \in \mathbb{N}$