Prove $3^{2n+1} + 2^{n+2}$ is divisible by $7$ for all $n\ge0$

Solution 1:

Your initial calculation can lead to an answer.

Our expression is equal to $3(9^n)+4(2^n)$. Note that $9\equiv 2\pmod{7}$, and therefore $9^n\equiv 2^n \pmod{7}$. It follows that $$3(9^n)+4(2^n)\equiv 3(2^n)+4(2^n)=7(2^n)\equiv 0\pmod{7}.$$

Solution 2:

$\rm \begin{eqnarray} {\bf Hint}\ \ \ a_{n\!+\!1}\!=2\,a_{n},\ b_{n\!+\!1}\!=9\,b_{n}\:\Rightarrow\: a_{n\!+\!1}\!+ b_{n\!+\!1} &\: =\: &\rm 2\ (\ a_{n}\!+b_{n}) + 7\,b_{n} \\ \rm hence\quad 7\mid a_{n\!+\!1}\!+ b_{n\!+\!1} &\rm \, if\, &\rm 7\mid a_{n}\!+b_{n}\end{eqnarray}$

Solution 3:

Note that $$3^{2n+1} = 3^{2n} \cdot 3^1 = 3 \cdot 9^n$$ and $$2^{n+2} = 4 \cdot 2^n$$ Note that $9^{3k} \equiv 1 \pmod{7}$ and $2^{3k} \equiv 1 \pmod{7}$.

If $n \equiv 0 \pmod{3}$, then $$3 \cdot 9^n + 4 \cdot 2^n \equiv (3+4) \pmod{7} \equiv 0 \pmod{7}$$ If $n \equiv 1 \pmod{3}$, then $$3 \cdot 9^n + 4 \cdot 2^n \equiv (3 \cdot 9 + 4 \cdot 2) \pmod{7} \equiv 35 \pmod{7} \equiv 0 \pmod{7}$$ If $n \equiv 2 \pmod{3}$, then $$3 \cdot 9^n + 4 \cdot 2^n \equiv (3 \cdot 9^2 + 4 \cdot 2^2) \pmod{7} \equiv 259 \pmod{7} \equiv 0 \pmod{7}$$

EDIT What you have written can be generalized a bit. In general, $$(x^2 + x + 1) \vert \left((x+1)^{2n+1} + x^{n+2} \right)$$ The case you are interested in is when $x=2$.

The proof follows immediately from the factor theorem. Note that $\omega$ and $\omega^2$ are roots of $(x^2 + x + 1)$.

If we let $f(x) = (x+1)^{2n+1} + x^{n+2}$, then $$f(\omega) = (\omega+1)^{2n+1} + \omega^{n+2} = (-\omega^2)^{2n+1} + \omega^{n+2} = \omega^{4n} (-\omega^2) + \omega^{n+2} = \omega^{n+2} \left( 1 - \omega^{3n}\right) = 0$$ Similarly, $$f(\omega^2) = (\omega^2+1)^{2n+1} + \omega^{2(n+2)} = (-\omega)^{2n+1} + \omega^{2n+4} = -\omega^{2n+1} + \omega^{2n+1} \omega^3 = -\omega^{2n+1} + \omega^{2n+1} = 0$$