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?
 A: 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.
A: $4^{2n+3}+3^{n+3} =16 \cdot 4^{2n+1}+3\cdot 3^{n+2}=16 \cdot(4^{2n+1}+ 3^{n+2})-13 \cdot 3^{n+2}$
A: $$4^{2n+3}+3^{n+3}= 16 \times 4^{2n+1} + 3 \times 3^{n+2} =13 \times 4^{2n+1} +3 \times(4^{2n+1}+3^{n+2})$$
A: $$\begin{gather}4^{2n+3}+3^{n+3}=4^{2n+1}\cdot{4^2}+3^{n+2}\cdot{3}=\\
=4^{2n+1}\cdot{4^2}+3^{n+2}\cdot{4^2}-3^{n+2}\cdot{4^2}+3^{n+2}\cdot{3}=\\
=16\cdot(4^{2n+1}+3^{n+2})-3^{n+2}\cdot(16-3)=\\
=16\cdot(4^{2n+1}+3^{n+2})-13\cdot3^{n+2}\end{gather}$$
A: Without induction, 
As $\displaystyle16\equiv3\pmod{13},16^n\equiv3^n$
$$4^{2n+1}+3^{n+2}=4\cdot16^n+9\cdot3^n\equiv3^n(4+9)\pmod{13}\equiv0$$
A: $$\quad{4^{2n+1}+3^{n+2} =\\4\times4^{2n} +9 \times 3^{n}=\\4 \times 16^{n} +9 \times 3^{n} =\\ 4 \times (13+3)^{n} +9\times 3^{n} \\
=4 (\left(\begin{matrix}n \\ 0\end{matrix}\right)13^n +\left(\begin{matrix}n \\ 1\end{matrix}\right)13^{n-1}*3 +...+\left(\begin{matrix}n \\ n-1\end{matrix}\right)13^{1}3^{n-1} +\left(\begin{matrix}n \\n\end{matrix}\right)3^n )+9*3^n\\
=4 (13q +\left(\begin{matrix}n \\n\end{matrix}\right)3^n )+9*3^n\\
=4 (13q +3^n )+9*3^n\\=4*13q+4*3^n+9*3^n=\\13q+13*3^n =13k}$$
it is a direct proof
