Comment démontrer une propriété… : En supposant la propriété aux rangs… — ECG1 approfondies | MetMat

Comment démontrer une propriété par récurrence double ou forte ?

En supposant la propriété aux rangs précédents (double/forte)

Démontrer une propriété $P(n)$ lorsque la relation de récurrence fait intervenir plusieurs rangs précédents.

Que ferais-tu face à un exercice de ce type ?

Soit $(u_n)$ définie par $u_0 = 0$ , $u_1 = 1$ et $u_{n+2} = 5u_{n+1} - 6u_n$ . Montrer que $\forall n \in \mathbb{N},\ u_n = 3^n - 2^n$ .

L'objectif

Démontrer une propriété $P(n)$ lorsque la relation de récurrence fait intervenir plusieurs rangs précédents.

Le principe

Si $P(n_0)$ et $P(n_0+1)$ sont vraies et si $\forall n \geq n_0,\ (P(n_0) \wedge \ldots \wedge P(n)) \Rightarrow P(n+1)$ , alors $\forall n \geq n_0,\ P(n)$ .

La méthode

1
Je pose $P(n)$ et je choisis entre récurrence double (dépendance à $n$ et $n-1$ ) ou récurrence forte (dépendance à tous les rangs $\leq n$ ).
2
Initialisation : je vérifie $P(n_0)$ (et $P(n_0+1)$ en récurrence double) par calcul direct.
3
Hérédité : je fixe $n$ et je suppose $P(k)$ vraie pour tout $k \in \{n_0, \ldots, n\}$ (forte) ou pour $k = n-1, n$ (double), puis j'en déduis $P(n+1)$ .
4
Je conclus par le principe de récurrence forte (ou double) que $\forall n \geq n_0,\ P(n)$ .

Pour comprendre, fais des exercices !

Exercice d'exemple

Soit $(u_n)$ définie par $u_0 = 0$ , $u_1 = 1$ et $u_{n+2} = 5u_{n+1} - 6u_n$ . Montrer que $\forall n \in \mathbb{N},\ u_n = 3^n - 2^n$ .

Étape 1 —

Je pose

P(n)

et je choisis entre récurrence double (dépendance à

n

n-1

) ou récurrence forte (dépendance à tous les rangs

\leq n

Je pose $P(n)$ : $u_n = 3^n - 2^n$ . La relation dépend de deux rangs, je fais une récurrence double.

Étape 2 —

Initialisation : je vérifie

P(n_0)

(et

P(n_0+1)

en récurrence double) par calcul direct.

Pour $n=0$ : $u_0 = 0$ et $3^0 - 2^0 = 0$ . Pour $n=1$ : $u_1 = 1$ et $3^1 - 2^1 = 1$ . Donc $P(0)$ et $P(1)$ sont vraies.

Étape 3 —

Hérédité : je fixe

n

et je suppose

P(k)

vraie pour tout

k \in \{n_0, \ldots, n\}

(forte) ou pour

k = n-1, n

(double), puis j'en déduis

P(n+1)

Soit $n \geq 0$ , supposons $P(n)$ et $P(n+1)$ . Alors $u_{n+2} = 5(3^{n+1} - 2^{n+1}) - 6(3^n - 2^n) = 3^n(15 - 6) - 2^n(10 - 6) = 9 \cdot 3^n - 4 \cdot 2^n = 3^{n+2} - 2^{n+2}$ .

Étape 4 —

Je conclus par le principe de récurrence forte (ou double) que

\forall n \geq n_0,\ P(n)

Par récurrence double, $\forall n \in \mathbb{N},\ u_n = 3^n - 2^n$ .

$u_n = 3^n - 2^n$ .

Les applications suivantes et la correction guidée sont réservées aux membres Premium

La méthode et sa première application corrigée restent en accès libre. Le Premium débloque les applications suivantes, l'aide IA et le suivi de ta maîtrise.