Prove that $3^{2n} +7$ is divisible by 8

Question

Prove by induction that $3^{2n} +7$ is divisible by 8 for $n \in \Bbb N$

So I think I have completed this proof but it doesn't seem very thorough to me - is my proof valid?

If $n=1$ then $3^{2n} +7 = 16 = 2(8)$ so true when $n=1$

Assume true for $n=k$ so $$ 8\vert 3^{2k} +7$$

If $n=k+1$ $$3^{2(k+1)} +7$$ $$3^{2k+2} +7$$ If $3^{2n} +7$ is divisble by 8 then $3^{2n} +7=8A$ where $A \in \Bbb Z$, and thus $3^{2k+2} +7=8B$ where $B \in \Bbb Z$ $$3^2 \times 3^{2k}+7$$ $$3^2 \times (8A)=72A$$ $$72A =8(9A)=9B$$

So by induction $3^{2n} +7$ is divisibe by 8 $\forall n \in \Bbb N$

Answer 1

No, it is not correct. It sholud be done something like this: $$3^{2k}= 8A-7$$ so\begin{eqnarray} 3^{2k+2}+7 &=& 9\cdot 3^{2k}+7\\ &=& 9\cdot (8A-7)+7 \\ &=& 72A-56\\ &=& 8(9A-7)\end{eqnarray}

Answer 2

You've got the right idea. Here's how to view the inductive step intuitively as multiplication

$$\begin{align} 3^{\large 2k} &= \color{#c00}{-7} + 8a\qquad {\rm i.e.}\ \ \ P(k)\\ \times\ \ \ \ \ 3^{\large 2} &= \ \ \ \color{#c00} 1 + 8\phantom{I_{I_{I_I}}}\\ \hline \Rightarrow\ \ 3^{\large 2(k+1)} &= {-7} + 8(\cdots)\ \ \ {\rm i.e.}\ \ P(k\!+\!1) \end{align}\qquad $$

Renark $\ $ Note $\, -7\! +\! 8a = 1\! +\! 8(a\!-\!1)\ $ so viewed this way, instead of $\, \color{#c00}{-7 \times 1}\,$ we get $\,1\times 1,\,$ so the above boils down to $\, (1+8j)(1+8k) = 1+8n,\,$ i.e. $\bmod 8\!:\ 1^2\equiv 1,\ $ so the result boils down to $\,9\equiv 1\,\Rightarrow\, 9^n\equiv 1^n\equiv 1\,$ by the Congruence Power Rule.

Answer 3

An option:

Step $n+1$:

$3^{2n+2}+7 =9 \cdot 3^{2n} +7=$

$(8+1)\cdot 3^{2n} +7=$

$(3^{2n}+7) +8;$

The first term is divisible by $8$ by hypothesis, so is the second term.

Answer 4

Posting this community wiki answer as a protest - instructors should not ask for proofs by induction when there are much more straightforward ones like $$ 3^{2n} + 7 = 9^n + 7 \equiv 1^n + 7 \equiv 0 \pmod{8} . $$

Save induction for questions where it's really important.

Answer 5

We can prove it like this : $$ 9^n + 7 = 9^n + \sqrt[n]{7}^n $$ And by using factorization : $$ 9^n + \sqrt[n]{7}^n = (9+7)(9^{n-1} -9^{n-2}\cdot7 + ... + 7^{n-1})$$ $$ 9^n + \sqrt[n]{7}^n = (16)(9^{n-1} -9^{n-2}\cdot7 + ... + 7^{n-1})$$ $$ \frac{9^n + 7}{16} = 9^{n-1} -9^{n-2}\cdot7 + ... + 7^{n-1}$$

We have $16$ divides $9^{n}+7$ and $8$ divides $16$, so $8$ divides $9^{n}+7$ which is the same as' $8$ divides $3^{2n}+7$'