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

$13\mid 4^{2\cdot 0+1}+3^{0+2}=4+9={13}^{}13\backslash mid4^\{2\backslash cdot0+1\}+3^\{0+2\}=4+9=13^\{\; \}$

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

$13\mid 4^{2n+3}+3^{n+3}13\; \backslash mid\; 4^\{2n\; +\; 3\}\; +\; 3^\{n\; +\; 3\}$

$13\mid 16\cdot 4^{2n+1}+3\cdot 3^{n+2}13\; \backslash mid\; 16\; \backslash cdot\; 4^\{2n\; +\; 1\}\; +\; 3\; \backslash cdot\; 3^\{n\; +\; 2\}$

$13\mid 13\cdot 4^{2n+1}+3\cdot 4^{2n+1}+3\cdot 3^{n+2}13\; \backslash mid\; 13\; \backslash cdot\; 4^\{2n\; +\; 1\}\; +\; 3\; \backslash cdot\; 4^\{2n\; +\; 1\}\; +\; 3\; \backslash cdot\; 3^\{n\; +\; 2\}$

$13\mid 13\cdot 4^{2n+1}+3\cdot (4^{2n+1}+3^{n+2})13\; \backslash mid\; 13\; \backslash cdot\; 4^\{2n\; +\; 1\}\; +\; 3\; \backslash 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.