Fiche de cours : Raisonnement par récurrence

Exemple rédigé : montrer que 3ⁿ ≥ 1 + 2n pour tout entier naturel n Initialisation (n = 0)3^0 = 1 et 1 + 2 \times 0 = 1, donc {3^0 \geq 1 + 2 \times 0} : la propriété est vraie au rang 0.
HéréditéSupposons la propriété vraie au rang k, c'est-à-dire :
3^k \geq 1 + 2k  (H.R.)
(H.R.) est l’abréviation d’hypothèse de récurrence : c’est ce que l’on suppose vrai au rang k, et c’est la seule chose que l’on aura le droit d’utiliser dans le calcul qui suit.
Démontrons qu'elle est alors vraie au rang {k+1}, c'est-à-dire :
3^{k+1} \geq 1 + 2(k+1)
\begin{aligned} 3^{k+1} &= 3 \times 3^k \\ &\geq 3(1 + 2k) \quad \text{(par H.R.)} \\ &= 3 + 6k \\ &\geq 1 + 2(k+1) \end{aligned}
car \begin{aligned}(3 + 6k) - \big(1 + 2(k+1)\big) &= 4k \\ &\geq 0\end{aligned}
Donc la propriété est vraie au rang {k+1}.
ConclusionLa propriété est vraie au rang 0 et héréditaire à partir de ce rang.
Donc, d'après le principe de récurrence, {3^n \geq 1 + 2n} pour tout n \in \mathbb{N}.

💡 Par quoi commencer l'hérédité ? Le point de départ dépend de la nature de la propriété, et c'est ce qui bloque le plus souvent :
• Une égalité (par exemple u_n = 1 - 3^n) : on part de la relation de récurrence, ici u_{k+1} = 3u_k - 2, puis on y remplace u_k par ce que donne l'hypothèse de récurrence.
• Une inégalité (par exemple {3^n \geq 1 + 2n}) : on part au contraire de l'hypothèse de récurrence elle-même, et on la transforme jusqu'au rang {k+1} : multiplier les deux membres par un nombre strictement positif, ou ajouter une même quantité aux deux membres, conserve le sens de l'inégalité.
Retiens la règle courte : égalité → on part de la relation de récurrence ; inégalité → on part de l'H.R. C'est exactement ce que fait l'exemple ci-dessus, qui démarre sur 3^k \geq 1 + 2k et le multiplie par 3.