Déjà plus de
1 million
d'inscrits !
Le raisonnement par récurrence
Déjà plus de
1 million
d'inscrits !
Avant de commencer, regarde les vidéos
Introduction :
En mathématiques, un certain nombre de propriétés dépendent d’un entier naturel .
Par exemple, la somme des entiers naturels de 1 à est égale à , c’est-à-dire que pour tout entier naturel :
Vérification de ce résultat pour et pour :
et
et
Même si on vérifie ce résultat jusqu’à , cela ne démontre pas qu’il est vrai pour tout . Pour effectuer cette démonstration, on dispose d’un outil particulier : le raisonnement par récurrence.
Le raisonnement par récurrence
Principe
Pour démontrer par récurrence qu’une proposition est vraie pour tout entier naturel supérieur ou égal à un entier naturel fixé, on procède en trois étapes.
Avant de commencer, on note la proposition que l’on va démontrer.
On vérifie que est vraie, c’est-à-dire que la proposition est vraie pour le premier indice . On dit qu’on a initialisé la récurrence.
On suppose que pour un entier quelconque , est vraie, et sous cette hypothèse (dite de récurrence) on démontre que la proposition est vraie. On a ainsi prouvé que l’hypothèse de récurrence « vraie » est héréditaire.
Lorsque les deux premières étapes ont été réalisées, on conclut : par récurrence, la proposition est vraie pour tout entier naturel .
Illustration
Démonstration de la formule vue en introduction à l’aide du raisonnement par récurrence :
Montrons que pour tout entier naturel ,
Notons la proposition :
La proposition est vraie car
On conçoit et on admet que si l’on sait démontrer que « vraie » entraîne « vraie », alors la proposition est vraie pour tout entier naturel .
Supposons donc que est vraie pour un entier naturel , c’est-à-dire que pour un entier naturel :
Montrons maintenant que la propriété est vraie au rang supérieur (au rang ), c’est-à-dire que est vraie.
Autrement dit, montrons que :
Comme est vraie, alors dans la somme , on peut remplacer les premiers termes par
On obtient alors :
En factorisant par , on obtient :
En réduisant le deuxième facteur au même dénominateur 2, on a :
Ainsi est vraie.
est vraie pour tout entier naturel , c’est-à-dire pour tout entier naturel ,
Exemples
Exemple 1
On considère la suite définie par et pour tout entier naturel ,
On montre par récurrence que tous les termes de la suite sont strictement positifs et que la suite est croissante.
Une suite est croissante si pour tout entier naturel ,
Il s’agit de démontrer que
Commençons par noter la proposition
et
On a bien donc
Supposons la proposition vraie pour un certain entier , c’est-à-dire :
Montrons que la proposition est vraie (c’est-à-dire : ), ce qui est équivalent, en utilisant la définition de la suite , à :
D’après l’hypothèse de récurrence :
On ajoute 1 aux inégalités :
Comme la fonction racine carrée est strictement croissante sur l’intervalle [0\ ; +∞[, on obtient :
Soit :
Par récurrence, la proposition est vraie pour tout entier naturel , donc la suite est croissante et à termes strictement positifs pour tout entier naturel .
Exemple 2
Démontrons que pour tout entier naturel : est divisible par .
Notons la proposition « est divisible par ».
Pour , on a et est bien divisible par
Supposons la proposition vraie pour un entier .
On a alors est divisible par , c’est-à-dire qu’il existe un nombre tel que
Pour montrer qu’un nombre est divisible par un entier , il faut montrer qu’il existe un nombre tel que
Montrons maintenant que la proposition est vraie au rang , c’est à dire que est aussi divisible par .
On a :
Comme le nombre est un entier alors on a bien en posant
Par récurrence, pour tout entier naturel , est vraie, donc pour tout entier naturel , est divisible par .
Exemple 3
Soit la suite définie par et pour tout entier naturel :
Démontrons que pour tout n∈ \mathbb N,
Notons la proposition « »
Pour , et
Donc la proposition est vraie.
Supposons la proposition vraie pour un entier , c’est-à-dire que pour un entier ,
On montre maintenant que la proposition est vraie au rang , c’est-à-dire que
Par définition de la suite , on a et d’après l’hypothèse de récurrence cela donne :
En réduisant au même dénominateur et en simplifiant par , on obtient :
ce qui est égal à
Par récurrence, pour tout entier naturel , est vraie, c’est-à-dire que pour tout entier naturel :