# Divisibility result by induction

by gmn_1450   Last Updated September 12, 2019 04:20 AM

Prove by induction that:

$$64 | 3^{2n + 2} - 8n - 9, n > 0$$

I've tried to manipulate $$P(k + 1)$$ and haven't come up with anything like $$P(k)$$.

$$P(k): 64 | 3^{2k + 2} - 8k - 9, k > 0$$ $$P(k+1): 64 | 3^{2(k+1) + 2} - 8(k+1) - 9$$

Tags :

Note that\begin{align}3^{2(k+1)+2}-8(k+1)-9&=9\times3^{2k+2}-8k-9-8\\&=8(3^{2k+2}-1)+3^{2k+2}-8k-9.\end{align}Now, you are assuming that $$64\mid3^{2k+2}-8k-9$$. So, all that remains to be proved is that $$64\mid8(3^{2k+2}-1)$$, which is equivalent to the assertion that $$8\mid3^{2k+2}-1$$. But that is easy, since $$3^{2k+2}=9^{k+1}=(8+1)^{k+1}$$.

If $$f(m)=3^{2n+2}-8n-9,$$

Eliminate $$3^{2n}$$ to establish $$f(m+1)-3^2f(m)$$ is actually divisible by $$64$$

$$\implies64|f(m+1)\iff64|9f(m)$$

Alternatively

If induction is not mandatory, we can use a more straight forward way using binomial expansion

$$3^{2n+2}=(1+8)^{n+1}\equiv1+\binom{n+1}18\pmod{8^2}$$