Notions de logique · Leçon 5

Raisonnement par récurrence

CalculSérie · Ex 7.1

$u_n = 7^n - 2^n$ : $u_1 = 5$ , $u_2 = 45$ , $u_3 = 335$ … Quel est le plus grand entier qui semble diviser tous les $u_n$ ( $n \geq 1$ ) ?

Tous les énoncés et corrigés

$u_n = 7^n - 2^n$ : $u_1 = 5$ , $u_2 = 45$ , $u_3 = 335$ … Quel est le plus grand entier qui semble diviser tous les $u_n$ ( $n \geq 1$ ) ?
Voir le corrigé
$5$
$u_1 = 5$ , donc le diviseur commun ne peut pas dépasser $5$ . Et $5$ semble diviser tous les termes : c'est la conjecture à démontrer.
La clé de l'hérédité
Pour faire apparaître $7^n - 2^n$ , quelle égalité est correcte ?
Voir le corrigé
- $7^{n+1} - 2^{n+1} = 7(7^n - 2^n) + 5 \cdot 2^n$
Remets dans l'ordre (attention aux pièges) : $5$ divise $7^n - 2^n$ .
Voir le corrigé
1. Initialisation : pour $n = 0$ , $7^0 - 2^0 = 0$ et $5$ divise $0$ . Donc $P(0)$ est vraie.
2. Hérédité : soit $n \in \mathbb{N}$ . Supposons que $5$ divise $7^n - 2^n$ : il existe $k \in \mathbb{Z}$ tel que $7^n - 2^n = 5k$ .
3. Alors $7^{n+1} - 2^{n+1} = 7(7^n - 2^n) + 5 \cdot 2^n = 35k + 5 \cdot 2^n = 5(7k + 2^n)$ .
4. Comme $7k + 2^n \in \mathbb{Z}$ , $5$ divise $7^{n+1} - 2^{n+1}$ : $P(n+1)$ est vraie.
5. Conclusion : d'après le principe de récurrence, pour tout $n \in \mathbb{N}$ , $5$ divise $7^n - 2^n$ .
Touche la ligne où ce raisonnement devient faux.
Voir le corrigé
Ligne 5 : L'initialisation n'a pas été faite, et elle est fausse : $10^0 + 1 = 2$ n'est pas divisible par $9$ .
Hérédité sans initialisation = des dominos qui se feraient tomber les uns les autres… mais dont aucun n'est poussé.
Pour montrer que $6$ divise $7^{2n} + 5^{2n+1}$ , lesquelles de ces égalités permettent de conclure l'hérédité ?
Voir le corrigé
- $7^{2n+2} + 5^{2n+3} = 49\,(7^{2n} + 5^{2n+1}) - 24 \cdot 5^{2n+1}$
- $7^{2n+2} + 5^{2n+3} = 25\,(7^{2n} + 5^{2n+1}) + 24 \cdot 7^{2n}$
Les deux premières sont correctes et $24$ est un multiple de $6$ . Il y a souvent plusieurs bonnes façons de faire apparaître l'hypothèse.
Pour $P(n)$ : « $7$ divise $3^{2n+1} + 2^{n+2}$ », calcule $3^{2n+1} + 2^{n+2}$ pour $n = 0$ (initialisation).
Voir le corrigé
$7$
$3^1 + 2^2 = 3 + 4 = 7$ , divisible par $7$ : $P(0)$ est vraie.
Soit $f$ définie par $f(0) = 3$ et $f(n+1) = 2f(n) + 5$ . Calcule $f(3)$ .
Voir le corrigé
$59$
$f(1) = 11$ , $f(2) = 27$ , $f(3) = 59$ . Et $2^{3+3} - 5 = 64 - 5 = 59$ : la formule $f(n) = 2^{n+3} - 5$ est cohérente.
Hérédité : on suppose $f(n) = 2^{n+3} - 5$ . Quel calcul de $f(n+1)$ est correct ?
Voir le corrigé
Soit $n \in \mathbb{N}$ . Supposons $f(n) = 2^{n+3} - 5$ . Alors $f(n+1) = 2f(n) + 5 = 2(2^{n+3} - 5) + 5 = 2^{n+4} - 5$ . Donc la propriété est vraie au rang $n + 1$ .
Teste $2^n \geq n^2$ pour $n = 0$ à $4$ . Pour quelle valeur est-elle fausse ?
Voir le corrigé
$3$
$2^3 = 8 < 9 = 3^2$ . C'est pour cela que la récurrence est initialisée à $n_0 = 4$ ( $16 \geq 16$ ).
On suppose $\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$ . Quel calcul est correct ?
Voir le corrigé
- $\sum_{k=1}^{n+1} k = \frac{n(n+1)}{2} + (n+1) = \frac{(n+1)(n+2)}{2}$
Énoncé piège : vraie ou fausse ?
$\forall n \in \mathbb{N}^{*},\ \forall x \in \mathbb{R} :\ (1+x)^n \geq 1 + nx$
Voir le corrigé
La proposition est fausse. Pour $n = 3$ et $x = -10$ : $(1 + x)^3 = -729$ et $1 + 3x = -29$ , or $-729 < -29$ .
Pour $n = 3$ , $x = -10$ : $(-9)^3 = -729 < -29$ . L'inégalité de Bernoulli n'est vraie que pour $x \geq -1$ : dans l'hérédité, on multiplie par $1 + x$ , qui doit être positif. L'énoncé de la série a oublié cette condition.

La clé de l'hérédité