Da $n\in {\mathbb{N}}_0$ ist der Induktionsanfang bei $n=0$:

$13|4^{2\cdot 0+1}+3^{0+2}=4+9={13}^{}$

Darauf folgt der Induktionsschluss mit $n\to n+1$:

$13|4^{2n+3}+3^{n+3}$

$13|16\cdot 4^{2n+1}+3\cdot 3^{n+2}$

$13|13\cdot 4^{2n+1}+3\cdot 4^{2n+1}+3\cdot 3^{n+2}$

$13|13\cdot 4^{2n+1}+3\cdot (4^{2n+1}+3^{n+2})$

Diese Summe ist durch 13 teilbar, da beide Summanden durch 13 teilbar sind. Beim ersten Summanden ist dies der Fall, da der Faktor 13 explizit davor steht. Der zweite Summand lässt sich durch 13 teilen, da er rechte Faktor gleich dem Induktionsanfang ist.