Raisonnement par récurrence — définition : Une récurrence démontre qu'une propriété vaut pour tous les entiers à partir d'un rang : on la teste au premier entier, puis on prouve qu'elle passe de n à n + 1.
Les trois étapes
- Initialisation : on vérifie la propriété pour le premier entier.
- Hérédité : on suppose la propriété vraie au rang n (hypothèse de récurrence) et on la démontre au rang n + 1.
- Conclusion : la propriété est vraie pour tout n à partir du premier rang.
L’image des dominos
Le premier domino tombe, et chaque domino qui tombe fait tomber le suivant : tous finissent par tomber.
Exemple résolu
Montrons que 1 + 3 + 5 + … + (2n − 1) = n². Pour n = 1, 1 = 1². Supposons la formule vraie au rang n. Alors, au rang n + 1, la somme vaut n² + (2n + 1) = (n + 1)². La propriété est donc vraie pour tout n ≥ 1.
Erreur fréquente
Oublier l’initialisation. Sans elle, l’hérédité seule ne prouve rien : la propriété « 10n + 1 est divisible par 9 » passe l’hérédité, mais elle est fausse dès n = 0, car 2 n’est pas divisible par 9.
Exemple : u₀ = 2, un+1 = un + 3 : montrer par récurrence que un = 2 + 3n.