accueil / sommaire cours terminale S / raisonnement par récurrence

I Raisonnement par récurrence

1) Exemple de raisonnement par récurrence

Soit a une constante réel > 0 fixe et quelconque.

Montrer que l'on a (1+a)ⁿ ≥ 1 + na pour tout naturel n.

L'énoncé "(1+a)ⁿ ≥ 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)⁰ ≥ 1 + 0 × a ? oui car (1 + a)⁰ = 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 entier n ≥ 0 (1+a)ⁿ ≥ 1 + na

2) Généralisation du raisonnement par récurrence

Soit n₀ un entier naturel fixe. P(n) un énoncé de variable n entier naturel défini pour tout entier n supérieur ou égale à n₀.

Si l'on demande de montrer que l'énoncé P(n) est vrai pour tout n supérieur ou égal à n₀, nous pouvons penser à un raisonnement par récurrence et conduire comme suit le raissonnement :

i) Vérifier que P(n₀) est vrai

ii) Montrer que quelque soit l'entier p ≥ n₀ tel que P(p) soit vrai, P(p+1) soit nécessairement vrai aussi

alors nous pouvons conclure que P(n) est vrai pour tout entier n ≥ n₀.

3) Exercices de récurrence

a) exercice de récurrence

énoncé de l'exercice : soit la suite numérique (u_n)_n>0 est définie par u₁ = 2 et pour tout n > 0 par la relation u_n+1 = 2u_n − 3. Démontrer que pour tout entier n > 0, u_n = 3 − 2ⁿ⁻¹.

Soit l'énoncé P(n) de variable n suivant : « u_n = 3 − 2ⁿ⁻¹ », 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 u₁ = 3 − 2¹⁻¹ ?

par définition u₁ = 2

et

3 − 2¹⁻¹ = 3 - 2⁰ = 3 - 1 = 2

donc u₁ = 3 − 2¹⁻¹ et P(1) est bien vrai.

ii) soit p un entier ≥ 1 tel que P(p) soit vrai, nous avons donc par hypothèse u_p = 3 − 2^p−1. Montrons alors que P(p+1) est vrai, c'est-à-dire que u_p+1 = 3 − 2^(p+1)−1.

calculons u_p+1

u_p+1 = 2u_p − 3 (définition de la suite)

u_p+1 = 2(3 − 2^p−1) − 3 (hypothèse de récurrence)

u_p+1 = 6 − 2 × 2^p−1 − 3 = 3 − 2^p−1+1 = 3 − 2^p

d'où P(p+1) est vrai

Conclusion : P(n) est vrai pour tout entier n > 0, nous avons pour tout n > 0 u_n = 3 − 2ⁿ⁻¹.

b) exercice démonstration par récurrence de la somme des entiers naturels impairs

énoncé de l'exercice : Calculer, pour tout enier n ≥ 2, la somme des n premiers naturels impairs.

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 premiers valeurs de n et éssayer de faire une conjecture sur le formule à démontrer (essayer de deviner la formule) et ensuite voir par récurrence si cette formule est valable.

pour tout n ≥ 2 , soit S_n la somme des n premiers naturels impairs.

S_n = 1 + 3 + 5 + 7 + ... + (2n − 1)

Calculons S(n) pour les premières valeurs de n.

S₂ = 1 + 3 = 4

S₃ = 1 + 3 + 5 = 9

S₄ = 1 + 3 + 5 + 7 = 16

S₅ = 1 + 3 + 5 + 7 + 9 = 25

S₆ = 1 + 3 + 5 + 7 + 9 + 11 = 36

pour n ∈ {2;3;4;5;6} , S_n = n²

A-t-on S_n = n² pour tout entier n ≥ 2 ?

Soit l'énoncé P(n) de variable n suivant : « S_n = n² » ; montons que P(n) est vrai pour tout n ≥ 2.

Récurrence :

i) P(2) est vrai on a S₂ = 1 + 3 = 4 = 2² .

ii) soit p un entier > 2 tel que P(p) est vrai, nous donc par hypothèse S_p = p² , montrons alors que S_p+1 est vrai., c'est que nous avons S_p+1 = (p+1)² .

Démonstration :

S_p+1 = S_p + (2(p+1) - 1) par définition de S_p

S_p+1 = S_p + 2p + 1

S_p+1 = p² + 2p + 1 d'après l'hypothède de récurrence

d'où S_p+1 = (p+1)²

CQFD

Conclusion : P(n) est vrai pour tout entier n ≥ 2, donc S_n = 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 http://www.les-suites.fr/somme-des-n-premiers-entiers.htm .

c) exercice sur les dérivées n ième

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 de la fonction ƒ⁽ⁿ⁾ pour tout entier n ≥ 1 .

Calculons les premières dérivées de la fonction ƒ. Rappel : (1/g)' = −g'/g² et (gⁿ)' = ngⁿ⁻¹g' .

∀ x ∈ D_ƒ , ƒ^'(x) = −1 / (x + 1)² = .

∀ x ∈ D_ƒ , ƒ^''(x) = (−1) × (−2) × / (x + 1)³ = 2 / (x + 1)³ =

∀ x ∈ D_ƒ , ƒ⁽³⁾(x) = 2 × (−3) / (x + 1)⁴ =

∀ x ∈ D_ƒ , ƒ⁽⁴⁾(x) = (−2 × 3 × −4) / (x + 1)⁵ = 2 × 3 × 4 / (x + 1)⁵ =

Pour n ∈ {1;2;3;4;} nous avons obtenu :

∀ x ∈ D_ƒ , ƒ⁽ⁿ⁾(x) = (−1)ⁿ n! / (x + 1)ⁿ⁺¹ =

soit P(n) l'énoncé de récurrence de variable n pour tout n ≥ 1 suivant :

« ƒ⁽ⁿ⁾(x) = (−1)ⁿ n! / (x + 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)² = (−1)¹ 1! / (x + 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 =

CQFD

P(p) est vrai pour tout entier p ≥ 1 .

Conclusion : P(n) est vrai pour tout entier n ≥ 1, donc :

pour tou entier n ≥ 1, et ∀ x ∈ D_ƒ , ƒ⁽ⁿ⁾(x) = (−1)ⁿ n! / (x + 1)ⁿ⁺¹ =