Exercices : le raisonnement par récurrence

Exercice 1

Réponse : Initialisation, hérédité, conclusion

On vérifie d’abord le premier rang (initialisation), puis on montre que la propriété se transmet d’un rang au suivant (hérédité), et on conclut.

Exercice 2

Réponse : Faux

Il faut aussi l’initialisation. Exemple : « 10ⁿ + 1 est divisible par 9 » est héréditaire car 10ⁿ⁺¹ + 1 = 10(10ⁿ + 1) − 9, mais elle est fausse pour n = 0 (10⁰ + 1 = 2), et en fait pour tout n.

Exercice 3

Réponse : 15

On applique la relation de récurrence trois fois.

1. u₁ = 2 × 1 + 1 = 3
2. u₂ = 2 × 3 + 1 = 7
3. u₃ = 2 × 7 + 1 = 15

Exercice 4

Réponse : hypothèse de récurrence · n + 1

L’hypothèse de récurrence est la supposition « P(n) est vraie » pour un n fixé ; on en déduit P(n + 1).

Exercice 5

Réponse : 5050

On applique la formule démontrée par récurrence avec n = 100.

1. 100 × 1012 = 10 1002 = 5 050

Exercice 6

Exemple de réponse : Soit P(n) : « u_n = 2ⁿ⁺¹ − 1 ».
Initialisation : 2¹ − 1 = 1 = u₀, donc P(0) est vraie.
Hérédité : soit n un entier tel que u_n = 2ⁿ⁺¹ − 1. Alors u_n+1 = 2u_n + 1 = 2(2ⁿ⁺¹ − 1) + 1 = 2ⁿ⁺² − 2 + 1 = 2ⁿ⁺² − 1. P(n + 1) est vraie.
Conclusion : par récurrence, u_n = 2ⁿ⁺¹ − 1 pour tout entier naturel n.

Dans l’hérédité, on part de u_n+1 = 2u_n + 1 et on remplace u_n grâce à l’hypothèse de récurrence.

• Tu as énoncé P(n).
• Tu as vérifié l’initialisation pour n = 0.
• Tu as utilisé l’hypothèse de récurrence dans le calcul de u_n+1.
• Tu as rédigé une conclusion.

Exercice 7

Exemple de réponse : Soit P(n) : « 1 + 3 + … + (2n − 1) = n² ».
Initialisation : pour n = 1, la somme vaut 1 et 1² = 1. P(1) est vraie.
Hérédité : soit n ≥ 1 tel que 1 + 3 + … + (2n − 1) = n². Alors 1 + 3 + … + (2n − 1) + (2n + 1) = n² + 2n + 1 = (n + 1)². P(n + 1) est vraie.
Conclusion : la propriété est vraie pour tout n ≥ 1.

Le terme ajouté au rang n + 1 est 2(n + 1) − 1 = 2n + 1, et n² + 2n + 1 = (n + 1)².

• Tu as identifié le terme suivant : 2(n + 1) − 1 = 2n + 1.
• Tu as reconnu l’identité remarquable (n + 1)².

Exercice 8

Exemple de réponse : Soit P(n) : « 4ⁿ − 1 est divisible par 3 ».
Initialisation : 4⁰ − 1 = 0 = 3 × 0. P(0) est vraie.
Hérédité : soit n tel que 4ⁿ − 1 = 3k avec k entier. Alors 4ⁿ⁺¹ − 1 = 4 × 4ⁿ − 1 = 4(4ⁿ − 1) + 3 = 12k + 3 = 3(4k + 1), divisible par 3.
Conclusion : pour tout n, 4ⁿ − 1 est divisible par 3.

L’astuce est d’écrire 4ⁿ⁺¹ − 1 = 4(4ⁿ − 1) + 3 pour faire apparaître l’hypothèse de récurrence.

• Tu as traduit « divisible par 3 » par « égal à 3k avec k entier ».
• Tu as fait apparaître 4ⁿ − 1 dans l’expression de 4ⁿ⁺¹ − 1.