🎲
Le principeLe raisonnement par récurrence permet de démontrer qu'une propriété P(n) est vraie pour tout entier n ≥ n0. Imaginez une file de dominos : si le premier tombe (initialisation) et que chaque domino fait tomber le suivant (hérédité), alors tous tombent. On formalise ainsi : on vérifie P(n0), puis on montre que si P(k) est vraie pour un k ≥ n0, alors P(k+1) est vraie. La conclusion s'impose alors pour tout n ≥ n0.
📖 Définition
Raisonnement par récurrence : méthode de démonstration pour une propriété dépendant d'un entier, en deux étapes.
📢 Rappel
Entier naturel : nombre entier positif ou nul (0, 1, 2, ...).
💡 À retenir : Initialisation + Hérédité = Conclusion universelle.
🔢
Exemple classiqueDémontrons que pour tout n ≥ 1, 1+2+...+n = n(n+1)/2. Initialisation : pour n=1, 1 = 1×2/2, vrai. Hérédité : supposons la formule vraie pour un entier k ≥ 1. Alors 1+2+...+k+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k/2 + 1) = (k+1)(k+2)/2, ce qui est exactement la formule au rang k+1. La propriété est donc héréditaire. Par récurrence, elle est vraie pour tout n ≥ 1.
⭐ À retenir
La somme des n premiers entiers naturels non nuls est n(n+1)/2.
🔍 Exemple
Pour n=100, la somme vaut 100×101/2 = 5050.
💡 À retenir : L'hérédité transforme k(k+1)/2 + (k+1) en (k+1)(k+2)/2.
📈
InégalitéProuvons que pour tout entier n ≥ 1, 2^n > n. Initialisation : n=1, 2^1 = 2 > 1, vrai. Hérédité : supposons 2^k > k pour un k ≥ 1. Alors 2^{k+1} = 2 × 2^k > 2k (par hypothèse). Comme k ≥ 1, on a 2k = k + k ≥ k + 1. Donc 2^{k+1} > k + 1. La propriété est héréditaire. Conclusion : pour tout n ≥ 1, 2^n > n.
📢 Rappel
Pour k ≥ 1, 2k ≥ k+1 car k ≥ 1.
⭐ À retenir
La propriété 2^n > n est vraie pour tout n ≥ 1.
💡 À retenir : L'astuce : 2k ≥ k+1 car k ≥ 1.
⚠️
Pièges à éviterAttention : une propriété peut être héréditaire sans être vraie ! Par exemple, P(n) : « n = n+1 » est héréditaire (si n = n+1, alors n+1 = n+2) mais jamais initialisée. Sans initialisation, l'hérédité ne prouve rien. Vérifiez toujours les deux étapes. Autre piège : ne pas confondre « supposer P(k) vraie pour un k quelconque » et « supposer P(k) vraie pour tous les k ». L'hypothèse de récurrence ne porte que sur un k fixé.
⭐ À retenir
Une propriété héréditaire non initialisée peut être fausse pour tout entier.
🔍 Exemple
P(n) : « n = n+1 » est héréditaire mais jamais vraie, car l'initialisation échoue.
💡 À retenir : Toujours vérifier l'initialisation et l'hérédité.