Déjà plus de
1 million
d'inscrits !
Raisonnement par récurrence
Déjà plus de
1 million
d'inscrits !
Avant de commencer, regarde la vidéo
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 à est égale à , c’est-à-dire que pour tout entier naturel :
Nous pouvons vérifier ce résultat pour et pour :
Pour :
Pour :
Même si ce résultat est vrai jusqu’à , cela ne démontre pas pour autant 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.
On vérifie que est vraie, c’est-à-dire que la proposition est vraie pour le premier indice .
On suppose que, pour un entier naturel quelconque , est vraie.
Sous cette hypothèse (dite de récurrence), on démontre que la proposition est vraie.
Lorsque les deux premières étapes ont été réalisées, on peut conclure.
En effet :
Illustration
Démontrons maintenant la formule vue en introduction à l’aide du raisonnement par récurrence et montrons que, pour tout entier naturel , .
La proposition est vraie, car .
On conçoit donc que, si l’on sait démontrer que, pour , « 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 (), c’est-à-dire que est vraie.
Autrement dit, montrons que :
Comme est vraie, dans la somme , on peut remplacer les premiers termes par .
est vraie pour tout entier naturel .
Exemples
La meilleure façon de se familiariser avec le raisonnement par récurrence, c’est de le travailler. Nous donnons donc ici quatre exemples d’un tel raisonnement.
Exemple 1
On considère la suite définie par et, pour tout entier naturel , .
Montrons 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 ici donc de démontrer que , pour tout entier naturel .
On a bien : , donc : .
Supposons la proposition vraie pour un certain entier naturel , c’est-à-dire :
Montrons que la proposition est vraie, c’est-à-dire que .
En utilisant la définition de la suite , c’est équivalent à :
Hypothèse de récurrence : | |
On ajoute aux inégalités : | |
Comme la fonction racine carrée est strictement croissante sur l’intervalle , elle ne change pas le sens des inégalités, et on obtient : | |
Soit : |
Par récurrence, la proposition est vraie pour tout entier naturel .
Exemple 2
Démontrons que, pour tout entier naturel , est divisible par .
Pour , on a :
est bien divisible par .
Supposons la proposition vraie pour un entier naturel .
Pour montrer qu’un entier est divisible par un entier , il faut montrer qu’il existe un entier tel que .
est divisible par , c’est-à-dire qu’il existe un entier relatif tel que .
Montrons maintenant que la proposition est vraie, c’est à dire que est aussi divisible par .
On cherche à montrer qu’il existe un entier relatif tel que .
Hypothèse de récurrence : | |
On soustrait à l’égalité : | |
De plus : | |
On remplace par : | |
On développe : | |
On factorise par : | |
étant un entier relatif, est donc aussi un entier relatif. Posons ainsi un entier relatif tel que . On obtient : |
Pour tout entier naturel , est vraie.
Exemple 3
Soit la suite définie par et, pour tout entier naturel , .
Démontrons que, pour tout , .
Pour :
Supposons la proposition vraie pour un entier naturel , c’est-à-dire que, pour un entier naturel :
Montrons maintenant que la proposition est vraie au rang , c’est-à-dire :
Hypothèse de récurrence : | |
Par définition de la suite : | |
On remplace par : | |
On réduit au même dénominateur le dénominateur du deuxième terme : | |
On simplifie par : | |
On factorise par : |
Pour tout entier naturel , est vraie.
Exemple 4 : inégalité de Bernoulli
L’inégalité de Bernoulli dit que, pour tout réel strictement positif et entier naturel, .
Nous utiliserons cette inégalité dans le cours suivant, sur les suites. Nous allons donc la démontrer ici, par récurrence.
Soit un réel strictement positif.
Pour :
Supposons la proposition vraie pour un entier naturel , c’est-à-dire, que pour un entier naturel :
Montrons maintenant que la proposition est vraie au rang , c’est-à-dire :
On a : | |
Hypothèse de récurrence : | |
D’où, en multipliant par (, donc , et cela ne change pas le sens des inégalités) : | |
On développe : | |
On factorise par : | |
étant un entier positif, : | |
D’où : |
Pour tout entier naturel , est vraie.
Conclusion :
Dans ce cours, nous avons vu ce principe puissant qu’est le raisonnement par récurrence : il permet de démontrer assez rapidement une propriété sur l’ensemble des entiers naturels, ou une partie de cet ensemble.
Ainsi, notamment en travaillant sur les suites, nous ferons souvent appel à ce type de raisonnement.