Raisonnement par récurrence

Nom:

Classe:

Date:

É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
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$ ?
3.
Vérifie $1 + 3 + 5 + \dots + (2n-1) = n^2$ pour $n = 6$ : que vaut $1 + 3 + 5 + 7 + 9 + 11$ ?
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
5.
Avant de démontrer $2^n > n$ , vérifie les premiers dominos : calcule $2^n$ pour $n = 1, 2, 3$ .
6.
Vérifie la formule $1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$ pour $n = 3$ .
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 ?
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$ .
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$
10.
Suis l'hérédité pour $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ avec des nombres, en prenant $k = 4$ .
11.
Suis l'hérédité pour $1 + 3 + \dots + (2n-1) = n^2$ avec des nombres, en prenant $k = 6$ .
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$
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$ .
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}$ .
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
16.
Suis l'hérédité pour $1 + 2 + \dots + 2^n = 2^{n+1} - 1$ avec des nombres, en prenant $k = 5$ .
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$ .
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.