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 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 . On considère une propriété (ou un prédicat) définie pour , telle que :
Initialisation : est vraie;
Hérédité : pour tout , , si est vraie, alors l’est aussi.
Alors, pour tout , , est vraie.
Démonstration
On considère l’ensemble .
On suppose que est non vide, il admet donc un plus petit élément que nous noterons qui est différent de (car est vraie). Alors m-1 n’est pas dans et donc l’entier suivant, , n’est pas non plus dans ce qui amène à une contradiction. On en déduit que est vide.
Exemple
Montrer que pour tout , la somme des premiers entiers naturels est égale à
Soit . Montrons par récurrence sur la propriété : . Initialisation : Pour , , la propriété est évidente. Hérédité : Soit . On suppose que est vraie, montrons que l’est encore. Par définition : D’après l’hypothèse de récurrence, on a : .
Ainsi : est bien vraie. D’après le principe de récurrence, la propriété est vraie pour tout .
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 . On considère une propriété (ou un prédicat) définie pour , telle que :
Initialisation : et sont vraies ;
Hérédité : pour tout , , si et sont vraies, alors l’est aussi.
Alors, pour tout , , est vraie.
Exemple
On considère la suite de Fibonacci définie par :
Soit . Montrons par récurrence double sur la propriété :
Initialisation : Pour et , la propriété est évidente.
Hérédité : Soit . On suppose que et sont vraies, montrons que l’est encore. On a : . La somme de deux entiers naturels non nuls est encore un entier naturel non nul, est bien vraie.
D’après le principe de récurrence double, la propriété est vraie pour tout .
La récurrence forte
Proposition
Soit . On considère une propriété (ou un prédicat) définie pour , telle que :
Initialisation : est vraie ;
Hérédité : pour tout , , si, pour tout , est vraie, alors l’est aussi.
Alors, pour tout , , est vraie.
Exemple
Montrons par récurrence forte sur , , la propriété : « admet une décomposition comme produit de nombres premiers ». Initialisation : est un nombre premier, donc est vraie. Hérédité : Soit , . On suppose que est vraie pour tout , montrons que l’est encore. Deux cas sont à considérer :
soit est premier, dans ce cas, est bien vraie ;
soit n’est pas premier, alors, il existe deux entiers et avec et tels que . Or, et sont vraies, donc et sont des produits de nombres premiers et aussi. est encore vraie.
D’après le principe de récurrence forte, la propriété est vraie pour tout , .
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.