Définition
Principe de récurrence
Le principe de récurrence est une méthode de preuve utilisée en mathématiques pour démontrer qu'une propriété est vraie pour tous les entiers naturels à partir d'un certain rang.
Initialisation
C'est la première étape de la démonstration par récurrence. Elle consiste à vérifier que la propriété est vraie pour la première valeur de l'entier, souvent notée n₀.
Hérédité
C'est la seconde étape du raisonnement par récurrence. Elle consiste à montrer que si la propriété est vraie à un rang k, alors elle l'est aussi au rang k + 1.
Rang
Le terme rang fait référence à la position d'un élément dans une suite ou à la valeur d'un entier particulier pour laquelle une propriété est étudiée.
Les Étapes de la Démonstration par Récurrence
1. L'Initialisation
La première étape dans une démonstration par récurrence est souvent simple. Elle consiste à vérifier manuellement que la propriété à démontrer est vraie pour le premier terme de la suite considérée. Ce premier terme est souvent le plus petit entier pour lequel la propriété doit être vérifiée. Par exemple, pour démontrer une propriété pour tous les entiers n ≥ 1, il faudra d'abord vérifier que la propriété est vraie pour n = 1.
2. L'Hérédité
Une fois l'initialisation effectuée, il faut montrer que si la propriété est vraie au rang k, alors elle est également vraie au rang suivant, c'est-à-dire k + 1. Cela implique que, sous l'hypothèse que la propriété est vraie pour un entier k quelconque (appelée 'l'hypothèse de récurrence'), on doit démontrer qu'elle est aussi vraie pour k + 1. Cette étape prouve que la validité de la propriété, une fois établie pour le premier cas, se propage de proche en proche pour tous les cas suivants.
Application de la Récurrence
Pour appliquer correctement une démonstration par récurrence, il est crucial de suivre méthodiquement les deux étapes décrites ci-dessus. Prenons la démonstration que la somme des n premiers entiers naturels est égale à n(n + 1)/2 :
1. **Initialisation** : Pour n = 1, la somme des 1 premiers entiers est 1, et cette valeur correspond bien à 1(1 + 1)/2.
2. **Hérédité** : Supposons qu'il existe un entier k tel que la somme des k premiers entiers naturels est k(k + 1)/2. Montrons que cela est vrai pour k + 1. La somme des k + 1 premiers entiers est 1 + 2 + ... + k + (k + 1). Par hypothèse de récurrence, la somme 1 + 2 + ... + k est k(k + 1)/2. Il suffit donc d'ajouter (k + 1) :
k(k + 1)/2 + (k + 1) = (k + 1)(k/2 + 1) = (k + 1)(k + 2)/2.
Ainsi, la propriété est vraie au rang k + 1 si elle est vraie au rang k. Par récurrence, elle est vraie pour tous les n ≥ 1.
A retenir :
La démonstration par récurrence est un outil essentiel en mathématiques, permettant de prouver que certaines propriétés valent pour une infinité de cas, en ne se concentrant que sur un cas de base initial et un transfert de propriété d'un rang au suivant. L'initialisation vérifie la validité de la propriété sur le premier rang donné, tandis que l'hérédité assure que la propriété est préservée d'un rang à l'autre, formant ainsi une chaîne ininterrompue de validité.
