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$



Answers 2


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

José Carlos Santos
José Carlos Santos
September 12, 2019 03:56 AM

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

lab bhattacharjee
lab bhattacharjee
September 12, 2019 03:56 AM

Related Questions


Prove that $n(n+1)(n+5)$ is a multiple of $6$

Updated March 06, 2016 03:08 AM


Proving that $7^n(3n+1)-1$ is divisible by 9

Updated August 15, 2017 18:20 PM