Comment démontrer une propriété… : En vérifiant l'initialisation et… — ECG1 approfondies | MetMat

Comment démontrer une propriété par récurrence simple ?

En vérifiant l'initialisation et l'hérédité

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

Maîtriser

Reconnaître

Résoudre

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

Montrer que $\forall n \in \mathbb{N},\ \sum_{k=0}^{n} k = \dfrac{n(n+1)}{2}$ .

L'objectif

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

Le principe

Si $P(n_0)$ est vraie et si $\forall n \geq n_0,\ P(n) \Rightarrow P(n+1)$ , alors $\forall n \geq n_0,\ P(n)$ est vraie.

La méthode

1
Je pose $P(n)$ : la propriété à démontrer pour $n \geq n_0$ , et je précise le rang initial $n_0$ .
2
Initialisation : je vérifie que $P(n_0)$ est vraie par un calcul direct.
3
Hérédité : je fixe $n \geq n_0$ , je suppose $P(n)$ vraie (hypothèse de récurrence) et je démontre $P(n+1)$ .
4
Je conclus par le principe de récurrence que $\forall n \geq n_0,\ P(n)$ est vraie.

Pour comprendre, fais des exercices !

Exercice d'exemple

Montrer que $\forall n \in \mathbb{N},\ \sum_{k=0}^{n} k = \dfrac{n(n+1)}{2}$ .

Étape 1 —

Je pose

P(n)

: la propriété à démontrer pour

n \geq n_0

, et je précise le rang initial

n_0

Je pose $P(n)$ : $\sum_{k=0}^{n} k = \dfrac{n(n+1)}{2}$ , avec $n_0 = 0$ .

Étape 2 —

Initialisation : je vérifie que

P(n_0)

est vraie par un calcul direct.

Pour $n = 0$ : $\sum_{k=0}^{0} k = 0$ et $\dfrac{0 \cdot 1}{2} = 0$ , donc $P(0)$ est vraie.

Étape 3 —

Hérédité : je fixe

n \geq n_0

, je suppose

P(n)

vraie (hypothèse de récurrence) et je démontre

P(n+1)

Soit $n \geq 0$ , supposons $\sum_{k=0}^{n} k = \dfrac{n(n+1)}{2}$ . Alors $\sum_{k=0}^{n+1} k = \dfrac{n(n+1)}{2} + (n+1) = \dfrac{(n+1)(n+2)}{2}$ .

Étape 4 —

Je conclus par le principe de récurrence que

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

est vraie.

Par récurrence, $\forall n \in \mathbb{N},\ \sum_{k=0}^{n} k = \dfrac{n(n+1)}{2}$ .

$\forall n \in \mathbb{N},\ \sum_{k=0}^{n} k = \dfrac{n(n+1)}{2}$ .

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.