À partir de quel rang ? $2^n$ contre $n^2$

On pose $P(n)$ : « $2^n>n^2$ ».

Initialisation. $2^5=32$ et $5^2=25$, donc $32>25$ : $P(5)$ est vraie.

Hérédité. Soit $n\ge 5$ fixé, supposons $P(n)$ vraie. Alors $2^{n+1}=2\times 2^n>2n^2$ par hypothèse de récurrence (on multiplie par $2>0$, ce qui conserve l'inégalité stricte). Il suffit donc de montrer $2n^2\ge (n+1{)}^2$, c'est-à-dire $2n^2-n^2-2n-1\ge 0$, soit $$n^2-2n-1\ge 0.$$ Le trinôme $n^2-2n-1$ vaut $(n-1{)}^2-2$, et pour $n\ge 5$ on a $(n-1{)}^2\ge 16>2$ : l'inégalité est acquise. Ainsi $2^{n+1}>2n^2\ge (n+1{)}^2$, donc $P(n+1)$.

Conclusion. $P(n)$ est vraie pour tout $n\ge 5$.

Les petits rangs. $2^2=4=2^2$ (égalité, donc pas d'inégalité stricte), $2^3=8<9$, $2^4=16=4^2$. L'inégalité est donc fausse pour $n=2$, $3$, $4$.

Ce que cela apprend. L'hérédité démontrée ci-dessus fonctionne pour tout $n\ge 5$ ; elle ne dit rien entre $2$ et $4$. Si l'on avait tenté d'initialiser en $n=2$, l'initialisation aurait échoué — et c'est heureux, puisque la propriété y est fausse. L'hérédité propage, elle ne démarre pas : c'est le rang initial, ici $5$, qui décide de ce que la récurrence démontre.