0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ rant mode on: I feel that this kind of proof by induction is meaningless, because it does not tell you why the statement is true. My answer tries to do that. $\endgroup$ – lhf Oct 10 '14 at 13:22
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Induction appears in the binomial theorem... $\endgroup$ – lhf Oct 10 '14 at 12:41
1
$\begingroup$

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)

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.