Exercice de raisonnement par récurrence

Mélodie - Mis à jour le 28/03/2022

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.

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.

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$

.

livre maths mpsi vuibert

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

2/5 - (1 vote)

Sommaire

Le principe de récurrence

Sur le même sujet

Comment calculer une moyenne en mathématiques ?

Comment calculer une moyenne en mathématiques ? 🤓

Tout savoir sur le nombre relatif

Tout savoir sur le nombre relatif 🔢

Tout savoir sur la racine carrée

Tout savoir sur la racine carrée 🤓

Mélodie

Journaliste

Hello ! Spécialisée dans toutes les questions de l'enseignement supérieur et l'orientation, j'espère que mes articles t'aideront à trouver ta voie et devenir la meilleure version de toi-même. Mes autres sujets de prédilection ? L'écologie, la science et la littérature.

Fiche de cours Prépa Prépa scientifique

Laisse-nous un commentaire !

Des questions ? Des bons plans à partager ? Nous validons ton commentaire et te répondons en quelques heures ! 🎉

C'est aussi pour toi !

Comprendre le cycle cellulaire

Comprendre le cycle cellulaire 🧬

Fiche de cours

Tout savoir sur le tableau d’avancement

Tout savoir sur le tableau d’avancement 🧪

Bac Fiche de cours

Le complément circonstanciel, le liant d’une phrase 🪶

Le complément circonstanciel, le liant d’une phrase 🪶

Fiche de cours Grammaire