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?
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'.