Prove that $7 | (3^{2n + 1} + 2^{n +2})$

Question

Prove that $7 | (3^{2n + 1} + 2^{n +2})$

So far I have:

Base case: n = 1

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

$ = (3^{3} + 2^{3})$

$ = (35)$ which divides 7

Inductive Step:

$ = (3^{2(n +1) + 1} + 2^{(n +1) +2})$

$ = (3^{2n + 3} + 2^{n + 3})$

$ 7j = (3^{2n + 3} + 2^{n + 3})$

-I'm a bit stuck as to how to proceed, any help or correcitons are appreciated. - I believe I understand where we need to go now but i'm not sure how to get there. It seems obvious that any n plugged into this formula would be divisible by 7 given that $3^1 + 2^2 = 7$ Since you have that $3^1+2^2$ nested inside the given formula it seems easily understood that any sum with any positive n would also be divisible by 7. I just don't see the steps in between to actually prove it.

Answer 1

Hint: if you want to use induction:

if $7\mid 3^{2k+1}+2^{k+2}=3\cdot 9^k+4\cdot 2^k$ for some $k\in\mathbb Z_{\ge 0}$, then:

$$3\cdot 9^{k+1}+4\cdot 2^{k+1}=2\left(3\cdot 9^k+4\cdot 2^k\right)+7\left(3\cdot 9^k\right)$$

Otherwise, if you know Modular Arithmetic:

$$3\cdot 9^n+4\cdot 2^n\equiv 3\cdot 2^n+4\cdot 2^n\equiv 7\cdot 2^n\equiv 0\pmod{7}$$

Answer 2

Let $7|3^{2k+1}+2^{k+2}$.

To prove that is divisible by $7|3^{2k+3}+2^{k+3}$, it suffices to prove that the difference is divided by $$\left((3^{2k+3}+2^{k+3})-(3^{2k+1}+2^{k+2}) \right)=\left((3^{2k+1+2}+2^{k+2+1})-(3^{2k+1}+2^{k+2}) \right)=$$ $$=\left(9 \cdot 3^{2k+1}+2\cdot 2^{k+2}-3^{2k+1}-2^{k+2} \right)=$$ $$=8 \cdot 3^{2k+1}+2^{k+2}=7 \cdot 3^{2k+1} +\left(3^{2k+1}+2^{k+2} \right)$$

Obviously, both terms are divisible by 7, the second induction hypothesis