En initialisant au rang de base, en supposant la propriété vraie au rang $n$ (hypothèse de récurrence), puis en la démontrant au rang $n+1$

Démontrer qu'une propriété $\mathcal{P}(n)$ est vraie pour tout entier $n \geq n_0$ .

L'objectif

Démontrer qu'une propriété $\mathcal{P}(n)$ est vraie pour tout entier $n \geq n_0$ .

Le principe

Le principe de récurrence affirme que si $\mathcal{P}(n_0)$ est vraie (initialisation) et si $\mathcal{P}(n) \Rightarrow \mathcal{P}(n+1)$ pour tout $n \geq n_0$ (hérédité), alors $\mathcal{P}(n)$ est vraie pour tout $n \geq n_0$ .

La méthode

1
Initialisation : vérifier que la propriété $\mathcal{P}(n_0)$ est vraie au rang de départ $n_0$ (souvent $n_0 = 0$ ou $n_0 = 1$ ).
2
Hypothèse de récurrence (H.R.) : supposer que $\mathcal{P}(n)$ est vraie pour un certain $n \geq n_0$ fixé (énoncer clairement cette hypothèse).
3
Hérédité : montrer que $\mathcal{P}(n+1)$ est vraie en utilisant l'hypothèse de récurrence et les relations vérifiées par la suite.
4
Conclusion : par le principe de récurrence, $\mathcal{P}(n)$ est vraie pour tout entier $n \geq n_0$ .

Pour comprendre, fais des exercices !

0/5 validés

Exercice d'exemple

Démontrer que $2^n \geq n + 1$ pour tout entier $n \geq 0$ .

Étape 1 —

Initialisation : vérifier que la propriété

\mathcal{P}(n_0)

est vraie au rang de départ

n_0

(souvent

n_0 = 0

n_0 = 1

Initialisation : pour $n = 0$ , $2^0 = 1$ et $0 + 1 = 1$ . On a $1 \geq 1$ . \checkmark

Étape 2 —

Hypothèse de récurrence (H.R.) : supposer que

\mathcal{P}(n)

est vraie pour un certain

n \geq n_0

fixé (énoncer clairement cette hypothèse).

H.R. : supposons que pour un certain $n \geq 0$ , on a $2^n \geq n + 1$ .

Étape 3 —

Hérédité : montrer que

\mathcal{P}(n+1)

est vraie en utilisant l'hypothèse de récurrence et les relations vérifiées par la suite.

Hérédité : montrons que $2^{n+1} \geq (n+1) + 1 = n + 2$ . On a $2^{n+1} = 2 \cdot 2^n \geq 2(n+1) = 2n + 2 \geq n + 2$ (car $n \geq 0$ implique $2n + 2 \geq n + 2$ ).

Étape 4 —

Conclusion : par le principe de récurrence,

\mathcal{P}(n)

est vraie pour tout entier

n \geq n_0

Conclusion : par le principe de récurrence, $2^n \geq n + 1$ pour tout $n \geq 0$ .

$2^n \geq n + 1$ pour tout $n \geq 0$ .

Application guidée

Soit $(u_n)$ définie par $u_0 = 0$ et $u_{n+1} = \sqrt{u_n + 2}$ . Démontrer que $u_n \geq 0$ pour tout $n \geq 0$ .

Application autonome 1

Démontrer que $\displaystyle\sum_{k=0}^{n} k = \dfrac{n(n+1)}{2}$ pour tout $n \geq 0$ .

Application autonome 2

Soit $(u_n)$ définie par $u_0 = 1$ et $u_{n+1} = \dfrac{u_n}{2} + 1$ . Démontrer que $1 \leq u_n \leq 3$ pour tout $n \geq 0$ .

Application autonome 3

Démontrer que pour tout $n \geq 1$ , $\dfrac{1}{1 \cdot 2} + \dfrac{1}{2 \cdot 3} + \cdots + \dfrac{1}{n(n+1)} = \dfrac{n}{n+1}$ .

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

En initialisant au rang de base, en supposant la propriété vraie au rang nnn (hypothèse de récurrence), puis en la démontrant au rang n+1n+1n+1

Pour comprendre, fais des exercices !

En initialisant au rang de base, en supposant la propriété vraie au rang $n$ (hypothèse de récurrence), puis en la démontrant au rang $n+1$