Prove by Induction $64\mid (7^{2n} + 16n − 1)$

Question

We have to show by Mathematical Induction that $64\mid (7^{2n} + 16n − 1).$

Progress :

Let us suppose $P(n)$ be the statement i.e.,

$P(n): 64\mid(7^{2n} + 16n − 1)$

For $n=1$,
$(7^{2\cdot 1} + 16\cdot 1 − 1=64$ which is divisible by $64$.
So, $P(1)$ is true.

Assume $P(k)$ be true,i.e.,

$64\mid (7^{2k} + 16k − 1)$.

Now for $n=k+1$

$7^{2(k+1)} + 16(k) − 1=49\cdot 7^{2k}+16k+15$.

How can I show this is divisible by $64$?

Answer 1

HINT:

$$7^{2m+2}+16(m+1)-1-7^2[7^{2m}+16m-1]=-16m(7^2-1)+16-1+7^2$$

$$\equiv0\pmod{64}$$

So, $64|(7^{2m+2}+16(m+1)-1) \iff64|(7^{2m}+16m-1)$

Answer 2

Use the fact of your induction hypothesis, we will break up your statement into parts that look like your induction hypothesis and parts that don't.
So, we have $49\cdot 7^{2k}+16k+15=48*7^{2k}+16+(7^{2k}+16k-1)$ Now, note that $16|48,16|16,$ and by your induction hypothesis, $16|7^{2k}+16k-1.$ Thus 16 divides the sum

Answer 3

Inductive Step:

$P(k)$ is true, verify $P(k+1)$:

$$\begin{array}{rcl} 7^{2(k+1)}+16(k+1)-1&=&49\cdot7^{2k}+16k+16-1\\ &=&49(7^{2k}+16k-1)-49(16k-1)+16k+15\\ &=&49(7^{2k}+16k-1)-48\cdot16k+64\\ &=&49(7^{2k}+16k-1)-12\cdot64k+64 \end{array}$$

All terms are divisible by $64$, so $64|7^{2(k+1)}+16(k+1)-1$, so the inductive step is proven and $P(k)$ is true.

Answer 4

By the binomial theorem, $7^{2n}=(8-1)^{2n}=8^2a-\binom{2n}{1}8+1=64a-16n+1$, hence the result.

Answer 5

Induction step: $7^{2(n+1)}+16(n+1)-1=49\cdot7^{2n}+16n+15$

By induction hypothesis $7^{2n}+16n-1$ is divisible by 64, so this is also true for $16(7^{2n}+16n-1)$.

Now we add this term to the term above and we obtain:

$49\cdot7^{2n}+16n+15=7^{2n}+16n+16 \cdot 16n-1=7^{2n}+16n-1=0 (\mod 64) $

(again by induction hypothesis)