🎯
Le principe des dominosLe raisonnement par récurrence permet de prouver qu'une propriété P(n) est vraie pour tous les entiers n à partir d'un certain rang. Imaginez une file de dominos : si le premier tombe (initialisation) et si chaque domino qui tombe fait tomber le suivant (hérédité), alors tous les dominos tombent. Cette analogie illustre parfaitement la structure d'une démonstration par récurrence. En mathématiques, on l'utilise pour démontrer des formules de sommes, des inégalités ou des propriétés sur les suites.
📢 Rappel
Les entiers naturels sont 0,1,2,... On note N. Une propriété dépendant de n peut être vraie ou fausse.
📖 Définition
L'hérédité est le fait que si la propriété est vraie pour un entier k, alors elle est vraie pour k+1.
💡 À retenir : Comme des dominos : un point de départ et une transmission de proche en proche.
📝
Les deux étapes clésOn considère une propriété P(n) définie pour tout entier n ≥ n₀. L'initialisation consiste à vérifier que P(n₀) est vraie. L'hérédité : on suppose que P(k) est vraie pour un certain entier k ≥ n₀ (c'est l'hypothèse de récurrence), puis on démontre que P(k+1) est vraie. Si ces deux étapes sont satisfaites, on conclut que P(n) est vraie pour tout n ≥ n₀. Cette structure est rigoureuse et doit être rédigée avec soin.
⭐ À retenir
Toujours écrire : « Supposons P(k) vraie pour un certain k ≥ n₀ » et non « pour tout k ».
🔍 Exemple
Pour n₀=0, initialisation : vérifier P(0). Hérédité : si P(k) vraie, alors P(k+1) vraie.
💡 À retenir : On passe de k à k+1 grâce à l'hypothèse de récurrence.
🧮
Un premier exempleDémontrons que pour tout n ≥ 1, 1+2+…+n = n(n+1)/2. Initialisation : pour n=1, 1 = 1×2/2 = 1, donc P(1) vraie. Hérédité : supposons P(k) vraie, c'est-à-dire 1+…+k = k(k+1)/2. Alors 1+…+k+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k/2 + 1) = (k+1)(k+2)/2, ce qui est exactement P(k+1). Conclusion : la formule est vraie pour tout n ≥ 1.
🔍 Exemple
Pour n=5, 1+2+3+4+5 = 15 et 5×6/2 = 15, la formule fonctionne.
💡 À retenir : L'hypothèse de récurrence permet de remplacer la somme des k premiers termes.
⚠️
Attention aux erreurs classiquesUne erreur fréquente est d'oublier l'initialisation : une propriété peut être héréditaire mais fausse pour tout n si le point de départ est faux. Par exemple, P(n) : « n > n » est héréditaire (si k > k alors k+1 > k+1) mais P(0) est fausse. Il faut aussi vérifier que l'hérédité est valable pour tout k ≥ n₀, pas seulement pour quelques valeurs. Enfin, rédigez clairement l'hypothèse de récurrence et la conclusion.
⭐ À retenir
Toujours vérifier l'initialisation avant de se lancer dans l'hérédité.
🔍 Exemple
P(n) : 2^n > n^2 pour n ≥ 5. Initialisation : 2^5=32 > 25, ok. Hérédité à démontrer.
💡 À retenir : Sans initialisation, la récurrence ne prouve rien.