Une récurrence sur une inégalité

Notons $\mathcal{P}(n)$ la proposition « $2^n\ge n+1$ », et démontrons-la pour tout entier $n\ge 1$.

Initialisation. Pour $n=1$ : $2^1=2$ et $n+1=2$. On a bien $2\ge 2$, donc $\mathcal{P}(1)$ est vraie.

Hérédité. Soit $n\ge 1$ un entier pour lequel $\mathcal{P}(n)$ est vraie, c'est-à-dire $2^n\ge n+1$. Multiplions cette inégalité par $2$, qui est strictement positif : le sens est conservé, donc $$2^{n+1}=2\times 2^n\ge 2(n+1)=2n+2.$$ Il reste à comparer $2n+2$ à $(n+1)+1=n+2$ : leur différence vaut $2n+2-(n+2)=n$, qui est positif puisque $n\ge 1$. Donc $2n+2\ge n+2$, et par transitivité $2^{n+1}\ge n+2$ : $\mathcal{P}(n+1)$ est vraie.

Conclusion. $\mathcal{P}(1)$ est vraie et $\mathcal{P}$ est héréditaire à partir de $1$ : par récurrence, $2^n\ge n+1$ pour tout entier $n\ge 1$.

Le point à retenir. Dans une récurrence sur une inégalité, l'hypothèse ne donne jamais le résultat voulu du premier coup : elle donne une minoration intermédiaire ($2n+2$), et il faut un second argument — ici « le reste $n$ est positif » — pour atteindre la cible.