I Raisonnement par récurrence
1) Exemple de raisonnement par récurrence
Soit a une constante réelle > 0 fixe et quelconque.
Montrer que l'on a (1+a)n ≥ 1 + na pour tout naturel n.
L'énoncé "(1+a)n ≥ 1 + na" est un énoncé de variable n, avec n entier ≥ 0, que l'on notera P(n).
Montrons que l'énoncé P(n) est vrai pour tout entier n ≥ 0.
P(0) est-il vrai ? A-t-on (1 + a)0 ≥ 1 + 0 × a ? Oui car (1 + a)0 = 1 et 1 + 0 × a = 1 ;
donc P(0) est vrai (i).
Soit p un entier ≥ 0 tel que P(p) soit vrai.
Nous avons, par hypothèse (1+a)p ≥ 1 + pa, alors P(p+1) est-il vrai ? A-t-on (1+a)p+1 ≥ 1 + (p+1)a ?
Nous utilisons l'hypothèse (1+a)p ≥ 1 + pa ;
d'où (1+a)(1+a)p ≥ (1+a)(1 + pa) car (1+a) est strictement positif ;
d'où (1+a)p+1 ≥ 1 + pa + a + pa² or pa² ≥ 0 ;
d'où (1+a)p+1 ≥ 1 + a(p+1).
L'énoncé P(p+1) est bien vrai.
Nous avons donc : pour tout entier p ≥ 0 tel que P(p) soit vrai, P(p+1) est vrai aussi (ii).
Conclusion :
P(0) est vrai ;
donc d'après (ii) P(1) est vrai ;
donc d'après (ii) P(2) est vrai ;
donc d'après (ii) P(3) est vrai ;
donc d'après (ii) P(4) est vrai ;
...
donc P(n) est vrai pour tout entier n ≥ 0, nous avons pour tout entier n ≥ 0 (1+a)n ≥ 1 + na.
2) Généralisation du raisonnement par récurrence
Soit n0 un entier naturel fixe. P(n) un énoncé de variable n entier naturel défini pour tout entier n supérieur ou égal à n0.
Si l'on demande de montrer que l'énoncé P(n) est vrai pour tout n supérieur ou égal à n0, nous pouvons penser à un raisonnement par récurrence et conduire comme suit le raisonnement :
i) Vérifier que P(n0) est vrai ;
ii) Montrer que, quel que soit l'entier p ≥ n0 tel que P(p) soit vrai, P(p+1) est nécessairement vrai aussi ;
alors nous pouvons conclure que P(n) est vrai pour tout entier n ≥ n0.
3) Exercices de récurrence
Exercice I.1
Soit la suite numérique (un)n>0 définie par u1 = 2 et pour tout n > 0 par la relation un+1 = 2un − 3. Démontrer que pour tout entier n > 0, un = 3 − 2n−1.
Exercice I.2 — démonstration par récurrence de la somme des entiers naturels impairs
Calculer, pour tout entier n ≥ 2, la somme des n premiers naturels impairs.
Exercice I.3 — dérivées n-ièmes
Cet exercice sur les dérivées n-ièmes n'est plus au programme actuel de Terminale (spécialité mathématiques) : c'est un exercice d'approfondissement.
Soit ƒ une fonction numérique définie sur l'ensemble de définition Dƒ = ]−∞ ; +∞[ \ {−1} par ƒ(x) = 1 / (x + 1) = . Déterminer la dérivée n-ième ƒ(n) de la fonction ƒ pour tout entier n ≥ 1.
Corrections
Correction de l'exercice I.1
Soit l'énoncé P(n) de variable n suivant : « un = 3 − 2n−1 », montrons qu'il est vrai pour tout entier n > 0.
Récurrence :
i) Vérifions que P(1) est vrai, c'est-à-dire a-t-on u1 = 3 − 21−1 ?
Par définition u1 = 2
et
3 − 21−1 = 3 − 20 = 3 − 1 = 2 ;
donc u1 = 3 − 21−1 et P(1) est bien vrai.
ii) Soit p un entier ≥ 1 tel que P(p) soit vrai, nous avons donc par hypothèse up = 3 − 2p−1. Montrons alors que P(p+1) est vrai, c'est-à-dire que up+1 = 3 − 2(p+1)−1.
Calculons up+1 :
up+1 = 2up − 3 (définition de la suite) ;
up+1 = 2(3 − 2p−1) − 3 (hypothèse de récurrence) ;
up+1 = 6 − 2 × 2p−1 − 3 = 3 − 2p−1+1 = 3 − 2p ;
d'où P(p+1) est vrai.
Conclusion : P(n) est vrai pour tout entier n > 0, nous avons pour tout n > 0 un = 3 − 2n−1.
Correction de l'exercice I.2
Nous pouvons penser à une récurrence puisqu'il faut établir le résultat pour tout n ≥ 2, mais la formule à établir n'est pas donnée.
Pour établir cette formule, il faut calculer les premières valeurs de Sn et essayer de faire une conjecture sur la formule à démontrer (essayer de deviner la formule) et ensuite voir par récurrence si cette formule est valable.
Pour tout n ≥ 2, soit Sn la somme des n premiers naturels impairs.
Sn = 1 + 3 + 5 + 7 + ... + (2n − 1).
Calculons Sn pour les premières valeurs de n.
S2 = 1 + 3 = 4 ;
S3 = 1 + 3 + 5 = 9 ;
S4 = 1 + 3 + 5 + 7 = 16 ;
S5 = 1 + 3 + 5 + 7 + 9 = 25 ;
S6 = 1 + 3 + 5 + 7 + 9 + 11 = 36.
Pour n ∈ {2 ; 3 ; 4 ; 5 ; 6}, Sn = n².
A-t-on Sn = n² pour tout entier n ≥ 2 ?
Soit l'énoncé P(n) de variable n suivant : « Sn = n² » ; montrons que P(n) est vrai pour tout n ≥ 2.
Récurrence :
i) P(2) est vrai on a S2 = 1 + 3 = 4 = 2².
ii) Soit p un entier ≥ 2 tel que P(p) est vrai, nous avons donc par hypothèse Sp = p², montrons alors que P(p+1) est vrai, c'est-à-dire que nous avons Sp+1 = (p+1)².
Démonstration :
Sp+1 = Sp + (2(p+1) − 1) par définition de Sp ;
Sp+1 = Sp + 2p + 1 ;
Sp+1 = p² + 2p + 1 d'après l'hypothèse de récurrence ;
d'où Sp+1 = (p+1)².
CQFD.
Conclusion : P(n) est vrai pour tout entier n ≥ 2, donc Sn = n² pour tout entier n ≥ 2.
Cette démonstration est à comparer avec la démonstration directe de la somme des n premiers impairs de la page la somme des n premiers entiers.
Correction de l'exercice I.3
Calculons les premières dérivées de la fonction ƒ. Rappel : (1/g)' = −g'/g2 et (gn)' = ngn−1g'.
∀ x ∈ Dƒ, ƒ'(x) = −1 / (x + 1)2 = .
∀ x ∈ Dƒ, ƒ''(x) = (−1) × (−2) / (x + 1)3 = 2 / (x + 1)3 = .
∀ x ∈ Dƒ, ƒ(3)(x) = 2 × (−3) / (x + 1)4 = .
∀ x ∈ Dƒ, ƒ(4)(x) = (−2 × 3) × (−4) / (x + 1)5 = 2 × 3 × 4 / (x + 1)5 = .
Pour n ∈ {1 ; 2 ; 3 ; 4} nous avons obtenu :
∀ x ∈ Dƒ, ƒ(n)(x) = (−1)n n! / (x + 1)n+1 = .
Soit P(n) l'énoncé de récurrence de variable n pour tout n ≥ 1 suivant :
« ƒ(n)(x) = (−1)n n! / (x + 1)n+1 = »,
montrons que cet énoncé est vrai pour tout entier n ≥ 1.
Récurrence :
i) P(1) est vrai puisque nous avons ƒ'(x) = −1 / (x + 1)2 = (−1)1 1! / (x + 1)1+1.
ii) Soit p un entier ≥ 1 tel que P(p) soit vrai, nous avons donc ∀ x ∈ Dƒ, ƒ(p)(x) = (−1)p p! / (x + 1)p+1, montrons que P(p+1) est vrai, c'est-à-dire que l'on a ∀ x ∈ Dƒ, ƒ(p+1)(x) = (−1)p+1 (p+1)! / (x + 1)p+2.
Démonstration :
∀ x ∈ Dƒ, ƒ(p+1)(x) = [ƒ(p)(x)]' = [(−1)p p! / (x + 1)p+1]' ;
∀ x ∈ Dƒ, ƒ(p+1)(x) = (−1)p p! [−(p+1)] / (x + 1)p+1+1 ;
∀ x ∈ Dƒ, ƒ(p+1)(x) = −(−1)p p! (p+1) / (x + 1)p+2 = (−1)p+1 (p+1)! / (x + 1)p+2 = ;
donc P(p+1) est vrai.
CQFD.
Conclusion : P(n) est vrai pour tout entier n ≥ 1, donc :
pour tout entier n ≥ 1 et ∀ x ∈ Dƒ, ƒ(n)(x) = (−1)n n! / (x + 1)n+1 = .