3 étapes pour le raisonnement par récurrence

Dans ce cours de mathématiques en ligne niveau Terminale S, ton e-prof de soutien scolaire te dévoile 3 étapes pour le raisonnement par récurrence.

Soit P(n) une propriété dépendant d’un entier naturel n, et n₀  un entier naturel fixé.
Pour démontrer que P(n) est vraie pour tout entier n ≥ n₀ on procède en trois étapes :

       1) Première étape : initialisation de la propriété

            On vérifie que P(n₀) est vraie.

        2) Deuxième étape : caractère héréditaire de la propriété

On démontre que si la propriété P(n) est vraie pour un entier n ≥ n₀ (hypothèse de récurrence) alors P(n+1) est également vraie.

        3) Troisième étape : conclusion

On conclut, par récurrence, que la propriété P(n) est vraie pour tout entier n ≥ n₀.

Exemple de raisonnement par récurrence

Démontrons par récurrence que pour tout entier naturel n, 7ⁿ – 1 est divisible par 6.

Notons P(n) la propriété « 7ⁿ – 1 est divisible par 6 », (cela revient à dire que 7ⁿ – 1 = 6k , avec k entier ).

Il faut montrer que la propriété P(n) est vraie pour tout entier naturel n c’est-à-dire il faut montrer que P(n) est vraie pour tout entier n ≥ 0 (n₀ = 0 ici).

Appliquons les trois étapes du raisonnement par récurrence à cet exemple :

• Première étape : initialisation de la propriété

Montrons que  P(n₀) = P(0) est vraie.

Pour n = 0, on a :

7ⁿ – 1 = 7⁰ – 1 = 1 – 1  = 0 = 6 × 0 => 7⁰ – 1 est bien un multiple de 6.

       On a montré que P(0) est vraie.

• Deuxième étape : caractère héréditaire de la propriété

Admettons que P(n) soit vraie c’est-à-dire supposons que 7ⁿ – 1 soit divisible par 6.

On suppose alors qu’il existe un entier k tel que 7ⁿ – 1 = 6k, ce qu’on peut écrire sous la forme 7ⁿ = 6k + 1 (1) : ceci sera notre hypothèse de récurrence.

Montrons qu’alors P(n+1) est vraie c’est-à-dire montrons que 7ⁿ⁺¹ – 1 est divisible par 6.

On a : 7ⁿ⁺¹ – 1 = 7 × 7ⁿ – 1

= 7 x (6k + 1) – 1  d’après l’hypothèse de récurrence (1)

= 7 x 6k + 7 – 1

= 6 x 7k + 6

= 6(7k + 1)            on pose k’ = 7k + 1

= 6k’

On vient de montrer que 7ⁿ⁺¹ – 1 = 6k’, c’est-à-dire on vient de montrer que 7ⁿ⁺¹ – 1 est divisible par 6 ce qui montre que P(n+1) est vraie.

On a démontré que si P(n) vraie alors P(n+1) vraie :

l’hérédité est donc bien vérifiée.

• Troisième étape : conclusion

Comme la propriété P(n) est vraie pour n = n₀ = 0 et comme P(n) est héréditaire pour tout entier n ≥ n₀ = 0, on en déduit par récurrence que la propriété P(n) est vraie pour tout entier n ≥ n₀ = 0, autrement dit on en déduit que pour tout entier n, 7ⁿ – 1 est divisible par 6.

Retrouve nos nombreux cours de mathématiques sur notre blog de soutien scolaire en ligne