Exercice de raisonnement par récurrence

Avant de présenter les raisonnements par récurrence, nous allons donner une propriété importante de l’ensemble des entiers naturels que nous admettrons.

Soit $\lambda$

< 0 Toute partie non vide de $\mathbb{N}$

admet un plus petit élément.

Conséquence : Il n’existe pas de suite infinie d’entiers naturels strictement décroissante.

Pour aller plus loin dans cette exploration et élever tes compétences en maths à un niveau supérieur, envisage l’opportunité d’apprendre avec un professeur particulier afin de dominer le raisonnement par récurrence. 👩‍🏫

Le principe de récurrence

La récurrence simple

Soit $n_0\in\mathbb{N}$

. On considère une propriété (ou un prédicat) $\mathcal{P}_n$

définie pour $n\in\mathbb{N}$

, $n\ge n_0$

telle que :

Initialisation : $\mathcal{P}_{n_0}$

est vraie;

Hérédité : pour tout $n\in\N$

, $n\ge n_0$

, si $\mathcal{P}_n$

est vraie, alors $\mathcal{P}_{n+1}$

l’est aussi.

Alors, pour tout $n\in\mathbb{N}$

, $n\ge n_0$

, $\mathcal{P}_n$

est vraie.

Démonstration

On considère l’ensemble $A =\big\{n \in\N,\;n\ge n_0,\; \mathcal{P}_n\text{ est fausse}\big\}$

.
On suppose que $A$

est non vide, il admet donc un plus petit élément que nous noterons $m$

qui est différent de $n_0$

(car $\mathcal{P}_{n_0}$

est vraie). Alors m-1 n’est pas dans $A$

et donc l’entier suivant, $m$

, n’est pas non plus dans $A$

ce qui amène à une contradiction. On en déduit que $A$

est vide.

Exemple

Montrer que pour tout $n\in\mathbb{N}$

, la somme $S_n$

des $n$

premiers entiers naturels est égale à $\dfrac{n(n+1)}{2}.$

Soit $n\in\mathbb{N}$

. Montrons par récurrence sur $n\in\mathbb{N}$

la propriété $\mathcal{P}_n$

: $S_n=\dfrac{n(n+1)}{2}$

.
Initialisation : Pour $n=0$

, $S_0=0$

, la propriété est évidente.
Hérédité : Soit $n\in\mathbb{N}$

. On suppose que $\mathcal{P}_n$

est vraie, montrons que $\mathcal{P}_{n+1}$

l’est encore. Par définition : $S_{n+1}=S_n+(n+1).$

D’après l’hypothèse de récurrence, on a : $S_n=\dfrac{n(n+1)}{2}$

.
Ainsi : $S_{n+1}=\dfrac{n(n+1)}{2}+n+1=\dfrac{(n+1)(n+2)}{2}.$

$\mathcal{P}_{n+1}$

est bien vraie. D’après le principe de récurrence, la propriété est vraie pour tout $n\in\mathbb{N}$

On va maintenant présenter deux variantes du raisonnement par récurrence : la récurrence double et la récurrence forte.

La récurrence double

Proposition

Soit $n_0\in\mathbb{N}$

. On considère une propriété (ou un prédicat) $\mathcal{P}_n$

définie pour $n\in\mathbb{N}$

, $n\ge n_0$

telle que :

Initialisation : $\mathcal{P}_{n_0}$

et $\mathcal{P}_{n_0+1}$

sont vraies ;

Hérédité : pour tout $n\in\N$

, $n\ge n_0$

, si $\mathcal{P}_n$

et $\mathcal{P}_{n+1}$

sont vraies, alors $\mathcal{P}_{n+2}$

l’est aussi.

Alors, pour tout $n\in\mathbb{N}$

, $n\ge n_0$

, $\mathcal{P}_n$

est vraie.

Exemple

On considère la suite de Fibonacci définie par : $u_0=0,\;u_1=1,\;\forall n\in\mathbb{N},\;u_{n+2}=u_{n+1}+u_n.$

Soit $n\in\mathbb{N}^*$

. Montrons par récurrence double sur $n\in\mathbb{N}^*$

la propriété $\mathcal{P}_n$

: $u_{n}\in\mathbb{N}^*$

Initialisation : Pour $n=1$

et $n=2$

, la propriété est évidente.

Hérédité : Soit $n\in\mathbb{N}^*$

. On suppose que $\mathcal{P}_n$

et $\mathcal{P}_{n+1}$

sont vraies, montrons que $\mathcal{P}_{n+2}$

l’est encore. On a : $u_{n+2}=u_{n+1}+u_{n}$

. La somme de deux entiers naturels non nuls est encore un entier naturel non nul, $\mathcal{P}_{n+2}$

est bien vraie.

D’après le principe de récurrence double, la propriété est vraie pour tout $n\in\mathbb{N}^*$

La récurrence forte

Proposition

Soit $n_0\in\mathbb{N}$

. On considère une propriété (ou un prédicat) $\mathcal{P}_n$

définie pour $n\in\mathbb{N}$

, $n\ge n_0$

telle que :

Initialisation : $\mathcal{P}_{n_0}$

est vraie ;

Hérédité : pour tout $n\in\mathbb{N}$

, $n\ge n_0$

, si, pour tout $k\in\llbracket n_0,n\rrbracket$

, $\mathcal{P}_k$

est vraie, alors $\mathcal{P}_{n+1}$

l’est aussi.

Alors, pour tout $n\in\mathbb{N}$

, $n\ge n_0$

, $\mathcal{P}_n$

est vraie.

Exemple

Montrons par récurrence forte sur $n\in\mathbb{N}$

, $n\ge 2$

, la propriété $\mathcal{P}_n$

: « $n$

admet une décomposition comme produit de nombres premiers ».
Initialisation : $2$

est un nombre premier, donc $\mathcal{P}_2$

est vraie.
Hérédité : Soit $n\in\mathbb{N}$

, $n\ge 2$

. On suppose que $\mathcal{P}_k$

est vraie pour tout $k\in\llbracket 2,n\rrbracket$

, montrons que $\mathcal{P}_{n+1}$

l’est encore. Deux cas sont à considérer :

soit $n+1$

est premier, dans ce cas, $\mathcal{P}_{n+1}$

est bien vraie ;

soit $n+1$

n’est pas premier, alors, il existe deux entiers $p$

et $q$

avec $2 \le p \le n$

et $2 \le q \le n$

tels que $n+1=pq$

. Or, $\mathcal{P}_p$

et $\mathcal{P}_q$

sont vraies, donc $p$

et $q$

sont des produits de nombres premiers et $n+1$

aussi. $\mathcal{P}_{n+1}$

est encore vraie.

D’après le principe de récurrence forte, la propriété est vraie pour tout $n\in\mathbb{N}$

, $n\ge 2$

Cet article est extrait de l’ouvrage Maths MPSI-MP2I. Tout-en-un : cours, méthodes, entraînement et corrigés (éditions Vuibert, juin 2021) écrit par E. Thomas, S. Bellec, G. Boutard. ISBN n°9782311408720