Raisonnement par récurrence

Échauffement

Trois questions rapides sur des leçons déjà vues.

Découvrir

On aligne des dominos. Le premier tombe, et chaque domino qui tombe fait tomber le suivant. Que se passe-t-il ?

Tous les dominos tombent
On ne peut rien dire

L'idée clé

Pour démontrer qu'une propriété $P_n$ est vraie pour tout entier $n \geq n_0$ , on procède en deux temps.

Initialisation : on vérifie que $P_{n_0}$ est vraie.

Hérédité : on suppose $P_n$ vraie pour un entier $n \geq n_0$ (hypothèse de récurrence), et on démontre $P_{n+1}$ .

Conclusion : $P_n$ est vraie pour tout $n \geq n_0$ .

Exemple corrigé

Soit $u_0 = 1$ et $u_{n+1} = 2u_n$ . Démontre que $u_n = 2^n$ pour tout $n \in \mathbb{N}$ .

u_0 = 1 = 2^0

: vrai.

Initialisation : on vérifie au rang 0.

Supposons

u_n = 2^n

pour un entier

n

.

Hérédité : on suppose la propriété au rang n.

u_{n+1} = 2u_n = 2 \times 2^n = 2^{n+1}

.

On utilise la relation, puis l'hypothèse.

Donc

u_n = 2^n

pour tout

n

.

Les deux étapes sont faites.

À toi, guidé

À toi : avec $u_0 = 3$ et $u_{n+1} = u_n + 2$ , on veut montrer que $u_n = 3 + 2n$ . Au rang $n = 0$ , que vaut $3 + 2n$ ?

3 + 2 \times 0

On remplace n par 0.

3

L'initialisation est vérifiée : c'est bien u₀.

Entraînement ★

Conclure pour tout $n$
Démontrer la propriété au rang $n + 1$ à l'aide de l'hypothèse
Supposer la propriété vraie à un rang $n$
Vérifier la propriété au premier rang

Attention !

Entraînement ★★

Soit $u_0 = 2$ et $u_{n+1} = 6u_n$ . On suppose que $u_n = 2 \times 6^n$ pour un entier $n$ . Avec cette hypothèse, quelle valeur obtient-on pour $u_{n+1}$ lorsque $n = 2$ ?
Soit $u_0 = 4$ et $u_{n+1} = 4u_n$ . On suppose que $u_n = 4 \times 4^n$ pour un entier $n$ . Avec cette hypothèse, quelle valeur obtient-on pour $u_{n+1}$ lorsque $n = 2$ ?
Soit $u_0 = 2$ et $u_{n+1} = 4u_n$ . On suppose que $u_n = 2 \times 4^n$ pour un entier $n$ . Avec cette hypothèse, quelle valeur obtient-on pour $u_{n+1}$ lorsque $n = 2$ ?

Pour démontrer par récurrence que $u_n = 7^n$ , avec $u_0 = 1$ et $u_{n+1} = 7u_n$ , qu'écrit-on au début de l'hérédité ?
1. Supposons que $u_n = 7^n$ pour un certain entier $n$ .
2. Supposons que $u_{n+1} = 7^{n+1}$ .
3. Supposons que $u_n = 7^n$ pour tout entier $n$ .
4. On vérifie que $u_0 = 1$ .
Pour démontrer par récurrence que $u_n = 5^n$ , avec $u_0 = 1$ et $u_{n+1} = 5u_n$ , qu'écrit-on au début de l'hérédité ?
1. Supposons que $u_n = 5^n$ pour un certain entier $n$ .
2. Supposons que $u_{n+1} = 5^{n+1}$ .
3. Supposons que $u_n = 5^n$ pour tout entier $n$ .
4. On vérifie que $u_0 = 1$ .

On démontre par récurrence que $1 + 2 + \dots + n = \dfrac{n(n + 1)}{2}$ . Pour passer du rang 8 au rang $9$ , quel nombre ajoute-t-on à la somme ?

Pour démontrer une propriété $P(n)$ pour tout $n \geq 0$ , on a prouvé : si $P(n)$ est vraie, alors $P(n + 1)$ est vraie. Que manque-t-il ?
1. L'initialisation : prouver $P(0)$
2. Rien : la démonstration est complète
3. Vérifier $P(n)$ pour quelques valeurs de plus

Bilan

Trois questions pour vérifier que c'est acquis.

Pour démontrer par récurrence que $u_n = 7^n$ , avec $u_0 = 1$ et $u_{n+1} = 7u_n$ , qu'écrit-on au début de l'hérédité ?
1. Supposons que $u_n = 7^n$ pour un certain entier $n$ .
2. Supposons que $u_{n+1} = 7^{n+1}$ .
3. Supposons que $u_n = 7^n$ pour tout entier $n$ .
4. On vérifie que $u_0 = 1$ .
Pour démontrer par récurrence que $u_n = 5^n$ , avec $u_0 = 1$ et $u_{n+1} = 5u_n$ , qu'écrit-on au début de l'hérédité ?
1. Supposons que $u_n = 5^n$ pour un certain entier $n$ .
2. Supposons que $u_{n+1} = 5^{n+1}$ .
3. Supposons que $u_n = 5^n$ pour tout entier $n$ .
4. On vérifie que $u_0 = 1$ .
Pour démontrer par récurrence que $u_n = 3^n$ , avec $u_0 = 1$ et $u_{n+1} = 3u_n$ , qu'écrit-on au début de l'hérédité ?
1. Supposons que $u_n = 3^n$ pour un certain entier $n$ .
2. Supposons que $u_{n+1} = 3^{n+1}$ .
3. Supposons que $u_n = 3^n$ pour tout entier $n$ .
4. On vérifie que $u_0 = 1$ .

Fiche résumé

Récurrence

Initialisation : $P_{n_0}$ est vraie.
Hérédité : si $P_n$ est vraie, alors $P_{n+1}$ est vraie.

Attention : sans initialisation, il n'y a pas de démonstration, même si l'hérédité marche.

À propos de cette leçon