# Proof by induction that $3^{2n} + 7$ is divisible by $4$

Demonstrate by induction: $3^{2n} + 7 = 4k$ is true, for any $n\in \mathbb N$. I need to demonstrate this using the induction principle.

So far I have:

$n = 1$

$$3^{2\cdot 1} + 7 = 4\cdot k$$ $$9 + 7 = 4k$$ $$16 = 4k$$ $$k = 4$$

So it checks for $n=1$.

$n = h$

$$3^{2\cdot h} + 7 = 4\cdot k$$

$n = h +1$

$$3^{2\cdot (h + 1)} + 7 = 4\cdot k'$$

(I use $k'$ to note that it's not the same $k$ as in $n = h$)

And I don't know how to continue.

• See here for a solution (just do the same for $3^{2n}+7$). – Dietrich Burde Jul 19 '15 at 17:48
• What is the relation between n and k, in other words, you did not define k( what is its domain?) – Socre Jul 19 '15 at 17:48
• Split $3^{2(h+1)}$ in two. Note it's much simpler with congruences. Actually you can prove it is equal to $8k$. – Bernard Jul 19 '15 at 17:49
• What I have to demonstrate is that is divisible by 4, so that's the same as saying something is equal to 4.k with k ∈ ℕ (I guess) – tobi Jul 19 '15 at 17:51
• Absolutely, but if you look at the proof in detail, you'll see it actually proves it's divisible by $8$. – Bernard Jul 19 '15 at 18:18

Be careful not to assume what you're trying to prove. After the induction hypothesis, i.e., $$3^{2h} + 7 = 4k \quad \textrm{for some } k,\tag1$$ you can't jump to $$3^{2(h+1)} + 7 = 4k' \quad \textrm{for some } k',\tag2$$ because that's what you must prove. Instead, start with just the left-hand side of $(2)$, and manipulate it so that you can use what you know from the hypothesis in $(1)$: \begin{align} 3^{2(h+1)} + 7 &= 3^{2h+2} + 7\\ &= 3^2 3^{2h} + 7\\ &= 9\cdot 3^{2h} + 7\\ &= 8\cdot 3^{2h} + \color{maroon}{3^{2h} + 7}\\ \end{align}

Can you take it from here?

You have shown for n=1 which is the first step so 👍 Now assume or state that it is true for n=h $$3^{2h}+7=4k$$ You want to show that it is true for n=h+1 So start with $3^{2h+2}+7$ $$3^{2h+2}+7= 9(3^{2h})+7=9(4k-7)+7$$ $$3^{2h+2}+7=36k-56=4(9k-14)=4m$$ where m is another natural number thus proving our assumption

Just to be contrary, here is a non-induction proof.

$\begin{array}\\ 3^{2n}+7 &=3^{2n}-1+8\\ &= (3^n+1)(3^n-1)+8 \end{array}$

Since $3^n$ is odd (for $n \ge 1$), $3^n-1$ and $3^n+1$ are consecutive even numbers, so one is exactly divisible by $2$ and the other is divisible by (at least) $4$.

Therefore, their product is divisible by at least 8, so $3^{2n}+7$ is divisible by 8.

Observe that $3^{2n} = 9^n = (9^n-1^n) + 1 = 8\cdot(...)+1=0+1 =1\pmod 4$, and $7 = 3 \pmod 4$, hence $3^{2n} + 7 = 1+3 = 4 = 0 \pmod 4$.

I'll give a proof with congruences: as $3^2\equiv 1\mod8$, $$3^{2^n}+7=(3^2)^n+7\equiv 1^n+7\equiv 0\mod 8.$$ A fortiori, $\;3^{2^n}+7\equiv 0\mod 4$.

$3^{2n} + 7 \equiv (-1)^{2n} + 7 \equiv 1^n+7 \equiv 0 \pmod 4$