Raisonnement par récurrence

Écris ta démarche pour chaque exercice.

1.
Quelles sont les deux parties que doit contenir toute démonstration par récurrence ?
1. a)Seulement la vérification des cas $n = 1$ à $n = 5$
2. b)Un contre-exemple et une contradiction
3. c)Une initialisation et une hérédité
4. d)Un tableau avec des affirmations et des justifications
Réponse: Une initialisation et une hérédité
Toute démonstration par récurrence a besoin d'une initialisation (le premier domino tombe) et d'une hérédité (chaque domino qui tombe fait tomber le suivant). Vérifier quelques cas n'est pas une démonstration, et les contre-exemples ou les tableaux relèvent d'autres méthodes.
2.
La formule $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ a été démontrée par récurrence. Vérifie-la pour $n = 5$ : que vaut $1 + 2 + 3 + 4 + 5$ ?
Réponse: 15
$1 + 2 + 3 + 4 + 5 = 15$ et $\dfrac{5 \cdot 6}{2} = 15$ . La formule donne la même valeur.
3.
Vérifie $1 + 3 + 5 + \dots + (2n-1) = n^2$ pour $n = 6$ : que vaut $1 + 3 + 5 + 7 + 9 + 11$ ?
Réponse: 36
$1 + 3 + 5 + 7 + 9 + 11 = 36 = 6^2$ , exactement comme le prévoit la formule.
4.
Dans l'image des dominos, que garantit l'hérédité ?
1. a)Tous les dominos ont la même taille
2. b)Le premier domino tombe
3. c)Chaque domino qui tombe fait tomber le suivant
4. d)Le dernier domino tombe
Réponse: Chaque domino qui tombe fait tomber le suivant
L'hérédité démontre $P(k) \Rightarrow P(k+1)$ : chaque fois qu'un domino tombe, le suivant tombe aussi. La chute du premier domino, c'est l'initialisation. Il n'y a pas de dernier domino, la rangée est infinie.
5.
Avant de démontrer $2^n > n$ , vérifie les premiers dominos : calcule $2^n$ pour $n = 1, 2, 3$ .
Réponse: 8
1. Que vaut $2^1$ ? (initialisation, compare avec $n = 1$ ) 2
2. Que vaut $2^2$ ? (compare avec $n = 2$ ) 4
3. Que vaut $2^3$ ? (compare avec $n = 3$ ) 8
6.
Vérifie la formule $1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$ pour $n = 3$ .
Réponse: 15
1. Calcule le membre de gauche $1 + 2 + 4 + 8$ . 15
2. Calcule $2^{3+1} = 2^4$ . 16
3. Calcule le membre de droite $2^4 - 1$ . 15
7.
Soit $P(n)$ la propriété $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ . Dans l'hérédité avec $k = 9$ , le membre de droite de $P(k+1)$ est $\dfrac{(k+1)(k+2)}{2}$ . Que vaut-il ?
Réponse: 55
$\dfrac{10 \cdot 11}{2} = 55$ . Vérification : l'hypothèse donne $1 + \dots + 9 = 45$ , et en ajoutant le terme suivant $10$ on obtient $55$ .
8.
Utilise la formule $1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$ , démontrée par récurrence, pour calculer $1 + 2 + 4 + 8 + 16 + 32 + 64$ .
Réponse: 127
Le dernier terme est $2^6$ , donc $n = 6$ et la somme vaut $2^7 - 1 = 128 - 1 = 127$ .
9.
Dans l'hérédité pour $1 + 3 + 5 + \dots + (2n-1) = n^2$ , quel terme ajoute-t-on à $1 + 3 + \dots + (2k-1)$ pour obtenir le membre de gauche de $P(k+1)$ ?
1. a) $2k + 1$
2. b) $k + 1$
3. c) $2k$
4. d) $2k - 1$
Réponse: $2k + 1$
Le dernier terme de $P(k+1)$ est $2(k+1) - 1 = 2k + 1$ . Le terme $2k - 1$ est déjà dans la somme, et $k + 1$ et $2k$ ne sont pas les nombres impairs de ce motif.
10.
Suis l'hérédité pour $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ avec des nombres, en prenant $k = 4$ .
Réponse: 15
1. D'après l'hypothèse, $1 + 2 + 3 + 4 = \dfrac{4 \cdot 5}{2}$ . Combien cela fait-il ? 10
2. Quel est le terme suivant $k + 1$ ? 5
3. Ajoute-le : quelle est la nouvelle somme $1 + 2 + 3 + 4 + 5$ ? 15
4. Que donne la formule pour $k + 1 = 5$ , c'est-à-dire $\dfrac{5 \cdot 6}{2}$ ? 15
11.
Suis l'hérédité pour $1 + 3 + \dots + (2n-1) = n^2$ avec des nombres, en prenant $k = 6$ .
Réponse: 49
1. D'après l'hypothèse, la somme des $6$ premiers nombres impairs vaut $6^2$ . Combien cela fait-il ? 36
2. Quel est le nombre impair suivant $2k + 1$ ? 13
3. Ajoute-le : quelle est la nouvelle somme ? 49
4. Que vaut $(k+1)^2 = 7^2$ ? 49
12.
Quelle phrase est la bonne hypothèse de récurrence pour démontrer $2^n > n$ pour tout $n \ge 1$ ?
1. a)Supposons $2^n > n$ pour tout $n \ge 1$
2. b)Supposons $2^k > k$ pour un entier $k \ge 1$
3. c)Supposons $2^{k+1} > k + 1$
4. d)Démontrer que $2^1 > 1$
Réponse: Supposons $2^k > k$ pour un entier $k \ge 1$
L'hypothèse de récurrence suppose la propriété pour un $k$ quelconque. La supposer pour tout $n$ ou pour $k + 1$ , c'est supposer ce qu'on veut démontrer, et $2^1 > 1$ est l'initialisation.
13.
L'hérédité pour " $n^3 - n$ est divisible par $3$ " utilise $(k+1)^3 - (k+1) = (k^3 - k) + 3k^2 + 3k$ . Vérifie-le avec $k = 4$ .
Réponse: 60
1. Que vaut $k^3 - k$ pour $k = 4$ ? 60
2. Que vaut $(k+1)^3 - (k+1)$ pour $k = 4$ ? 120
3. Que vaut la différence $120 - 60$ ? 60
4. Que vaut $3k^2 + 3k$ pour $k = 4$ ? 60
14.
Par récurrence, on peut aussi démontrer que $n^3 - n$ est divisible par $6$ . Pour $n = 6$ , calcule $\dfrac{6^3 - 6}{6}$ .
Réponse: 35
$6^3 - 6 = 216 - 6 = 210$ et $210 \div 6 = 35$ , un nombre entier, comme le prévoit la propriété.
15.
Un élève "démontre" que $1 + 2 + \dots + n = \dfrac{n(n+1)}{2} + 1$ pour tout $n \ge 1$ . Le calcul de l'hérédité est juste. Qu'est-ce qui ne va pas ?
1. a)L'hypothèse doit être $P(k+1)$ , pas $P(k)$
2. b)Rien, la propriété est vraie
3. c)L'initialisation échoue : pour $n = 1$ , le membre de gauche vaut $1$ et celui de droite $2$
4. d)On ne peut pas utiliser la récurrence pour des sommes
Réponse: L'initialisation échoue : pour $n = 1$ , le membre de gauche vaut $1$ et celui de droite $2$
Pour $n = 1$ : le membre de gauche vaut $1$ , celui de droite $\dfrac{1 \cdot 2}{2} + 1 = 2$ . L'initialisation échoue, donc la chaîne ne démarre jamais. En fait, l'affirmation est fausse pour tout $n$ , car la vraie somme est $\dfrac{n(n+1)}{2}$ .
16.
Suis l'hérédité pour $1 + 2 + \dots + 2^n = 2^{n+1} - 1$ avec des nombres, en prenant $k = 5$ .
Réponse: 127
1. D'après l'hypothèse, $1 + 2 + \dots + 2^5 = 2^6 - 1$ . Combien cela fait-il ? 63
2. Quel est le terme suivant $2^{k+1} = 2^6$ ? 64
3. Ajoute-le : quelle est la nouvelle somme ? 127
4. Que vaut $2^{k+2} - 1 = 2^7 - 1$ ? 127
17.
L'hérédité pour $2^n > n$ utilise la chaîne $2^{k+1} = 2 \cdot 2^k > 2k \ge k + 1$ . Suis-la avec $k = 5$ .
Réponse: 6
1. Que vaut $2^k = 2^5$ ? 32
2. Que vaut $2^{k+1} = 2 \cdot 2^5$ ? 64
3. Que vaut $2k$ ? 10
4. Que vaut $k + 1$ ? 6
18.
La formule $1 \cdot 2 + 2 \cdot 3 + \dots + n(n+1) = \dfrac{n(n+1)(n+2)}{3}$ se démontre par récurrence. Fais son initialisation et une étape d'hérédité avec des nombres.
Réponse: 40
1. Initialisation : que vaut le membre de droite pour $n = 1$ , c'est-à-dire $\dfrac{1 \cdot 2 \cdot 3}{3}$ ? (Le membre de gauche vaut $1 \cdot 2 = 2$ .) 2
2. Hypothèse pour $k = 3$ : que vaut $\dfrac{3 \cdot 4 \cdot 5}{3}$ ? 20
3. Quel est le terme suivant $(k+1)(k+2)$ pour $k = 3$ ? 20
4. Ajoute-le à la valeur de l'hypothèse. Quelle est la nouvelle somme ? (Compare avec $\dfrac{4 \cdot 5 \cdot 6}{3}$ .) 40