Divisibilité par 3

Initialisation. $4^0+5=6=3\times 2$.

Hérédité. Supposons $3\mid 4^n+5$, disons $4^n+5=3q$. Alors

$$4^{n+1}+5=4\times 4^n+5=4(4^n+5)-15=12q-15=3(4q-5),$$

divisible par $3$.

Conclusion. La propriété vaut pour tout $n\in \mathbb{N}$.

Plus court, par congruences. $4\equiv 1(\mathrm{mod}3)$, donc $4^n\equiv 1^n=1$, et $4^n+5\equiv 1+5=6\equiv 0(\mathrm{mod}3)$. La récurrence n'est que la version détaillée de ce calcul — mais elle a l'avantage de ne rien supposer d'autre que les opérations élémentaires.