Pour démontrer qu’une proposition $P(n)$ est vraie pour tout entier naturel $n$, on utilise un raisonnement adapté à la nature des entiers naturels appelé raisonnement par récurrence.
MéthodeRaisonnement par récurrence
Ce raisonnement procède toujours en trois étapes :
- Fondation : On vérifie que la proposition est vraie pour $n=0$. Cette étape permet d’initialiser la propriété.
- Hérédité : Soit $k$ un entier naturel fixé. On suppose la proposition vraie au rang $k$ (hypothèse de récurrence) et on montre qu’alors, elle est vraie au rang $(k+1)$. Cette étape consiste donc à montrer que la propriété est héréditaire.
- Conclusion : La proposition est vraie pour $n=0$, par hérédité elle est donc vraie pour $n=1$, puis pour $n=2$… et de proche en proche pour tous les entiers naturels.
Exemple
Si on reprend l’image d’une échelle :
- l’étape d’initialisation consiste à mettre le pied sur le premier barreau ;
- l’étape d’hérédité consiste à vérifier que l’on est capable de passer d’un barreau au barreau suivant ;
- Avec ces deux propriétés, on vérifie que l’on peut gravir la totalité de l’échelle et rejoindre n’importe quel barreau, aussi haut soit-il !
Remarque
Si le problème que nous avons à résoudre est la démonstration d’une propriété $P(n)$, non plus pour tout entier naturel $n$, mais pour tout entier supérieur (ou égal) à $1$ ou de manière plus général pour tout entier supérieur (ou égal) à $n_0$, nous adapterons la méthode : la fondation se fera non plus au rang $0$ mais au rang $n_0$ et pour l’hérédité, nous la démontrerons pour un entier $k$ supérieur (ou égal) à $n_0$.