Le raisonnement par récurrence

Le raisonnement par récurrence

Pour démontrer par récurrence qu’une proposition $(P_n)$ est vraie pour tout entier naturel $n$ supérieur ou égal à un entier naturel $n_0$ fixé, on procède en trois étapes.

• Étape 1 : Initialisation

On vérifie que $(P_{n0})$ est vraie, c’est-à-dire que la proposition est vraie pour le premier indice $_0$. On dit qu’on a initialisé la récurrence.

• Étape 2 : Hérédité

On suppose que pour un entier $n>n_0$, $(P_n)$ est vraie. Sous cette hypothèse, dite de récurrence, on démontre que la proposition $(P_{n+1})$ est vraie. On a ainsi prouvé que l’hypothèse de récurrence « $(P_n)$ vraie » est héréditaire.

Attention : cette étape est à faire pour un entier $n$ sinon on admet dès la démonstration ce qu’on veut justement démontrer.

• Étape 3 : Conclusion

Lorsque les deux premières étapes ont été réalisées, on conclut : par récurrence, la proposition $(P_n)$ est vraie pour tout entier naturel $n (n>n_0)$