Comment démontrer une propriété dépendant d'un entier par récurrence ? | MetMat

Comment démontrer une propriété dépendant d'un entier par récurrence ?

En menant une récurrence forte ou à deux pas lorsque $P(n+1)$ dépend de plusieurs rangs antérieurs

Démontrer une propriété $P(n)$ dont l'hérédité nécessite de connaître $P$ à plusieurs rangs antérieurs, typiquement pour les suites récurrentes d'ordre 2.

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

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

L'objectif

Démontrer une propriété $P(n)$ dont l'hérédité nécessite de connaître $P$ à plusieurs rangs antérieurs, typiquement pour les suites récurrentes d'ordre 2.

Le principe

Principe de récurrence forte : si $P(n_0)$ est vraie et si $\forall n \geq n_0, \bigl(\forall k \in \{n_0, \dots, n\}, P(k)\bigr) \Rightarrow P(n+1)$ , alors $\forall n \geq n_0, P(n)$ . Variante « à deux pas » : on initialise $P(n_0)$ et $P(n_0 + 1)$ puis on suppose $P(n)$ et $P(n+1)$ pour démontrer $P(n+2)$ .

La méthode

1
J'énonce $P(n)$ et je choisis le type de récurrence (forte ou à deux pas) selon le nombre de rangs antérieurs intervenant dans la formule de récurrence.
2
Initialisation : je vérifie $P(n_0)$ , et si besoin $P(n_0 + 1)$ , par calcul direct.
3
Hérédité renforcée : je suppose $P(k)$ vraie pour tout $k$ entre $n_0$ et $n$ (ou pour $P(n)$ et $P(n+1)$ à deux pas), puis j'en déduis $P(n+1)$ (respectivement $P(n+2)$ ).
4
Je conclus par le principe de récurrence forte (ou à deux pas) que $P(n)$ est vraie pour tout $n \geq n_0$ .

Pour comprendre, fais des exercices !

0/5 validés

Exercice d'exemple

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

Étape 1 —

J'énonce

P(n)

et je choisis le type de récurrence (forte ou à deux pas) selon le nombre de rangs antérieurs intervenant dans la formule de récurrence.

Je pose $P(n) : u_n = 2^{n+1} - 1$ . La récurrence $u_{n+2} = 3u_{n+1} - 2u_n$ fait intervenir deux rangs antérieurs, donc je choisis une récurrence à deux pas.

Étape 2 —

Initialisation : je vérifie

P(n_0)

, et si besoin

P(n_0 + 1)

, par calcul direct.

Initialisation : $u_0 = 1 = 2^1 - 1$ et $u_1 = 3 = 2^2 - 1$ ; $P(0)$ et $P(1)$ sont vraies.

Étape 3 —

Hérédité renforcée : je suppose

P(k)

vraie pour tout

k

entre

n_0

n

(ou pour

P(n)

P(n+1)

à deux pas), puis j'en déduis

P(n+1)

(respectivement

P(n+2)

Hérédité : je suppose $P(n)$ et $P(n+1)$ , soit $u_n = 2^{n+1} - 1$ et $u_{n+1} = 2^{n+2} - 1$ . Alors $u_{n+2} = 3(2^{n+2} - 1) - 2(2^{n+1} - 1) = 3 \cdot 2^{n+2} - 2 \cdot 2^{n+1} - 1 = 3 \cdot 2^{n+2} - 2^{n+2} - 1 = 2 \cdot 2^{n+2} - 1 = 2^{n+3} - 1$ , ce qui est $P(n+2)$ .

Étape 4 —

Je conclus par le principe de récurrence forte (ou à deux pas) que

P(n)

est vraie pour tout

n \geq n_0

Par récurrence à deux pas, $P(n)$ est vraie pour tout $n \in \mathbb{N}$ .

$\forall n \in \mathbb{N}, \;u_n = 2^{n+1} - 1$ .

Application guidée

Montrer par récurrence forte que tout entier $n \geq 2$ admet un diviseur premier.

Application autonome 1

Soit $(F_n)$ la suite de Fibonacci : $F_0 = 0, F_1 = 1, F_{n+2} = F_{n+1} + F_n$ . Montrer que $\forall n \in \mathbb{N}, \;F_n \leq 2^n$ .

Application autonome 2

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

Application autonome 3

Soit $(v_n)$ définie par $v_0=3$ , $v_1=5$ et $v_{n+2}=3v_{n+1}-2v_n$ pour tout $n\geq 0$ . Montrer par récurrence à deux pas que $\forall n\in\mathbb{N},\;v_n=2^{n+1}+1$ .

Crée ton compte pour accéder à la fiche et aux exercices

En menant une récurrence forte ou à deux pas lorsque P(n+1)P(n+1)P(n+1) dépend de plusieurs rangs antérieurs

Pour comprendre, fais des exercices !

En menant une récurrence forte ou à deux pas lorsque $P(n+1)$ dépend de plusieurs rangs antérieurs