<s>[INST] Is this proof by induction that $13 \mid 4^{2n+1}+3^{n+2}$ correct/sufficient? To show: $13\, |\, 4^{2n+1}+3^{n+2}$
I used induction beginning successfully with $n=0$ $($or $n=1),$
then making the step to $n+1:$
An $x$ exists so that $13x = 4^{2n+3}+3^{n+3}$
$$\begin{align*}13x &= 16\cdot4^{2n+1}+3\cdot3^{n+2}\\
\frac{13}{3}x &= \frac{16}{3}\cdot4^{2n+1}+3^{n+3}\\
\frac{13}{3}x &= \frac{13}{3}\cdot4^{2n+1}+4^{2n+1}+3^{n+3}\end{align*}$$
Here comes the actual question: Can I say that because of the premise the last two summands can be expressed as $13m$ with $m$ being a natural number? Like this:
$$\begin{align*}\frac{13}{3}x &= \frac{13}{3}\cdot4^{2n+1}+13m\\
x &= 4^{2n+1}+3m,\end{align*}$$ which is a natural number.
Is that a valid proof?
 [/INST] Yes, it seems to be correct. However, the person who would read the proof might be confused a little. Instead, you can re-write it differently, like
$$
\frac{4^{2n+3} + 3^{n+3}}{13} = \frac{13 \cdot 4^{2n+1} + 3\left(4^{2n+1} + 3^{n+1} \right)}{13} = \frac{13\cdot 4^{2n+1} + 3 \cdot 13m}{13} \in \mathbb{Z}
$$
which is the same, except it's going from 'bottom up'.
</s>