Prove $3^{2n+1} + 2^{n+2} = 7m$

Question

I'm trying to prove that $3^{2n+1} + 2^{n+2}$ is a multiple of 7 by using induction.

So I started to prove it for $n=1$: $3^{2(1)+1}+2^{1+2}=3^3+2^3=27+8=35=7(5)$.

Next, try to prove that the statement being true $n=k$ implies it being true for $n=k+1$. Thus:

$3^{2(k+1)+1}+2^{(k+1)+2} = 3^{2k+3}+2^{k+3} = (3)(3)(3^{2k+1})+(2)(2^{k+2}) = 9(3^{2k+1})+2(2^{k+2})$

I feel like I'm almost there, if I could've factor 9 and 2 somehow I could say that $3^{2k+1}+2^{k+2}=7m$ for some integer $m$, but I can't find a way to do it. What am I missing? Or did I do a blunder somewhere along the road?

Thanks in advance.

Answer 1

$$9(3^{2k+1}) + 2(2^{k+2}) = 7(3^{2k+1}) + 2(3^{2k+1}) + 2(2^{k+2}) = 7(3^{2k+1}) + 2(3^{2k+1} + 2^{k+2}) = 7(3^{2k+1} + 2m)$$

Answer 2

Good start! Hint: Consider what $3^{2(k+1)+1} + 2^{(k+1)+2} - 2(3^{2k+1} + 2^{k+2})$ is, and see where that gets you.

Answer 3

Alt. hint (no induction): $3\;\cdot 9^n+ 4 \cdot 2^n=3\cdot (7 + 2)^n+4 \cdot 2^n=3 \cdot 7 \cdot (\ldots)+ (3 + 4) \cdot 2^n\,$.

Answer 4

Base case. $n=1$; $3^{3}+2^3=35$ which is a multiple of $7$.

Inductive hypothesis. Assume true for $n$; that is $3^{2n+1}+2^{n+2}=7m$ for $m\in\Bbb N$.

Induction step. Try for $n+1$. We have $$\begin{align} 3^{2(n+1)+1}+2^{n+1+2}&=3^{2n+3}+2^{n+3}\\ &=9\cdot3^{2n+1}+2\cdot 2^{n+2}\\ &=9\cdot3^{2n+1}+2\cdot(7m-3^{2n+1})\\ &=9\cdot3^{2n+1}+14m-2\cdot3^{2n+1}\\ &=7\cdot3^{2n+1}+14m\\ &=7(3^{2n+1}+2m), \end{align}$$

and we are done.

Answer 5

$$9(3^{2k+1})=7(3^{2k+1})+2(3^{2k+1})$$ Hence we get: $$7(3^2k+1)+2(3^2k+1)+2(2^k+2)$$

Which we can see as a multiple of $7$ plus the result of $n=k$, which we assumed to be a multiple of $7$, multiplied by $2$.

Answer 6

the trick to induction is put the $k+1$ expression in terms of the $k$ expression.

If $ 3^{2k+1} + 2^{k+2}=7m$ then

$3^{2(k+1)+1}+2^{(k+1)+2} = 9(3^{2k+1})+2(2^{k+2}) = 2[ 3^{2k+1} + 2^{k+2}] + 7*3^{2k+1}$

$= 2(7m) + 7*3^{2k+1} = 7(2m + 3^{2k+1})$.

Answer 7

For a non-inductive solution, note that $3^2\equiv 2 \bmod 7$; then

$\begin{align} 3^{2n+1} + 2^{n+2} &\equiv 3\cdot 2^n + 4\cdot 2^n \\ &\equiv 7\cdot 2^n \bmod 7\\ \end{align}$