Le raisonnement par récurrence est une méthode de démonstration puissante pour prouver qu'une propriété est vraie pour tous les entiers naturels. Il repose sur un principe simple : si une propriété est vraie pour un premier entier (souvent 0 ou 1) et que, chaque fois qu'elle est vraie pour un entier, elle l'est aussi pour le suivant, alors elle est vraie pour tous les entiers.
1Principe du raisonnement par récurrence
Le raisonnement par récurrence comporte deux étapes :
- Initialisation : on vérifie que la propriété est vraie pour le premier entier (souvent n = 0 ou n = 1).
- Hérédité : on suppose que la propriété est vraie pour un entier k (hypothèse de récurrence) et on démontre qu'elle est alors vraie pour k+1.
Si ces deux étapes sont vérifiées, la propriété est vraie pour tous les entiers à partir du premier.
À retenir
L'initialisation est souvent simple, mais ne l'oublie pas ! Sans elle, la récurrence ne tient pas.
2Exemple détaillé
Montrons que pour tout entier n ≥ 1, la somme des n premiers entiers est : 1 + 2 + ... + n = n(n+1)/2.
Initialisation : pour n = 1, 1 = 1×2/2 = 1. Vrai.
Hérédité : supposons la propriété vraie pour un entier k ≥ 1. Alors 1+2+...+k = k(k+1)/2. Montrons qu'elle est vraie pour k+1 : 1+2+...+k+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k/2 + 1) = (k+1)(k+2)/2. C'est exactement la formule pour n = k+1. Donc l'hérédité est vérifiée.
Par récurrence, la formule est vraie pour tout n ≥ 1.
Astuce
Dans la démonstration de l'hérédité, pars toujours de l'hypothèse de récurrence et ajoute le terme suivant.
3Rédaction type
Pour rédiger correctement une démonstration par récurrence, suis ce plan :
- Énonce la propriété P(n) à démontrer.
- Initialisation : vérifie P(0) ou P(1).
- Hérédité : suppose P(k) vraie pour un entier k, puis démontre P(k+1).
- Conclusion : par récurrence, P(n) est vraie pour tout n.
Attention
N'oublie pas de préciser l'ensemble des entiers sur lequel tu travailles (par exemple n ≥ 0 ou n ≥ 1).
L'essentiel à retenir
- Le raisonnement par récurrence permet de prouver une propriété pour tous les entiers naturels.
- Il comprend deux étapes : initialisation et hérédité.
- L'initialisation vérifie la propriété pour le premier entier.
- L'hérédité suppose la propriété vraie pour k et la démontre pour k+1.
- Une rédaction claire et structurée est essentielle.
