Prove that $4^{2n+1}+3^{n+2} : \forall n\in\mathbb{N}$ is a multiple of $13$ How to prove that $\forall n\in\mathbb{N},\exists k\in\mathbb{Z}:4^{2n+1}+3^{n+2}=13\cdot k$
I've tried to do it by induction. For $n=0$ it's trivial.
Now for the general case, I decided to throw the idea of working with $13\cdot k$ and try to prove it via congruences. So I'd need to prove that $4^{2n+1}+3^{n+2}\equiv0\pmod{13} \longrightarrow 4^{2n+3}+3^{n+3}\equiv0\pmod{13}$, that is, $4^{2n+1}+3^{n+2}\equiv4^{2n+3}+3^{n+3}\pmod{13}$
But I have no clue how to do is. Any help?

Since you can use congruence arithmetic, you can exploit it to the hilt to prove it more simply
$\qquad\qquad\qquad \begin{eqnarray}{\rm mod}\ 13\!:\,\ 4^{2n+1}\!+3^{n+2} &=\,& 4\cdot \color{#0a0}{16}^n +\, \color{#c00}9\cdot 3^n \\ &\equiv\,& 4\,\cdot\, \color{#0a0}3^n\, \color{#c00}{-\,4} \cdot 3^n\equiv 0\quad {\bf QED} \\
\ \ {\rm by}\ \ &&\!\!\!\!\!\color{#0a0}{16}\equiv \color{#0a0}3,\,\ \color{#c00}{-4}\equiv \color{#c00}{9}\end{eqnarray}$
That $\color{#0a0}{\,16\equiv 3\,\Rightarrow\,16^n\equiv 3^n}$ follows by by the Congruence Power Rule (below), i.e. by inductive application of  Congruence Product Rule.  Notice how structuring the proof in this (congruence) arithmetical form makes the induction obvious: $ $ congruent numbers have congruent powers. 
This illustrates the great power of congruence arithmetic - it enables reuse of our well-honed knowledge of integer arithmetic to simplify many problems that are innately arithmetical. 
Congruence Product Rule $\rm\quad\ A\equiv a,\ \ and \ \  B\equiv b\ \Rightarrow\ \color{#c00}{AB\equiv ab}\ \ \ (mod\ m)$
Proof $\rm\ \ m\: |\: A\!-\!a,\ B\!-\!b\ \Rightarrow\ m\ |\ (A\!-\!a)\ B + a\ (B\!-\!b)\ =\ \color{#c00}{AB - ab} $
Congruence Power Rule $\rm\qquad \color{}{A\equiv a}\ \Rightarrow\ \color{blue}{A^n\equiv a^n}\ \  (mod\ m)$
Proof $\ $ It is true for $\rm\,n=1\,$ and $\rm\,A\equiv a,\ A^n\equiv a^n \Rightarrow\, \color{blue}{A^{n+1}\equiv a^{n+1}},\,$ by the Product Rule, therefore the result follows by induction on $\,n.$
See this answer for further congruence arithmetic rules and their proofs.
