1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ See here for a solution (just do the same for $3^{2n}+7$). $\endgroup$ – Dietrich Burde Jul 19 '15 at 17:48
  • 1
    $\begingroup$ What is the relation between n and k, in other words, you did not define k( what is its domain?) $\endgroup$ – Socre Jul 19 '15 at 17:48
  • $\begingroup$ Split $3^{2(h+1)}$ in two. Note it's much simpler with congruences. Actually you can prove it is equal to $8k$. $\endgroup$ – Bernard Jul 19 '15 at 17:49
  • 1
    $\begingroup$ 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) $\endgroup$ – tobi Jul 19 '15 at 17:51
  • $\begingroup$ Absolutely, but if you look at the proof in detail, you'll see it actually proves it's divisible by $8$. $\endgroup$ – Bernard Jul 19 '15 at 18:18
5
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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