<s>[INST] Problem with divisibility Proof of the following without induction :
$13| 3^{n+2}   +   4^{2n+1}$              
for every $n \in \mathbb{Z}^+$
Any help is apprciated.
 [/INST] First, rewrite as:
$$\begin{align}3^{n+2} + 4^{2n+1} &= 9\cdot3^n + 4\cdot4^{2n}\\
&= 9\cdot3^n + 4\cdot16^{n}\end{align}$$
Then, use modular arithmetic to prove divisibility by $13$:
$$\begin{align}9\cdot3^n + 4\cdot16^{n}&= 9\cdot3^n + 4\cdot(13+3)^n\\
&\equiv 9\cdot3^n + 4\cdot3^n\pmod{13}\\
&= 3^n\cdot(9 + 4)\pmod{13}\\
&= 3^n\cdot13\pmod{13}\\
&\equiv 0 \pmod{13}\end{align}$$
Hence, $3^{n+2} + 4^{2n+1} \equiv 0 \pmod{13}$, i.e. $13 | (3^{n+2} + 4^{2n+1})$ for all non-negative integers $n$.
</s>