Raisonnement par récurrence
I- Introduction :
Le raisonnement par récurrence est utilisé pour montrer des résultats faisant intervenir une variable entière de l'ensemble
ou d'une partie de cet ensemble, comme par exemple
,
etc.
Cette démonstration s'effectue en trois étapes :
L'étape
initialisation : Montrer que le résultat est vrai pour le tout premier rang (en général le premier rang est 0, mais il se peut que le premier rang soit 1, 2 ou autre, cela dépend du résultat à démontrer).
L'étape
hérédité : Montrer que le résultat est héréditaire, c'est-à-dire montrer que le résultat peut être "transmis" d'un rang fixé quelconque
au rang suivant
.
La conclusion
Pour expliquer ce principe assez intuitivement, prenons les deux exemples suivants :
Exemple 1 : La file de dominos
Si l'on pousse le premier domino de la file (Initialisation).
Et si les dominos sont posés l'un après l'autre d'une manière à ce que la chute d'un domino entraîne la chute de son suivant (Hérédité).
Alors :
Tous les dominos de la file tombent. (la conclusion)
Exemple 2 : L'échelle
Si on sait monter le premier barreau de l'echelle (Initialisation).
Et si l'on sait toujours passer d'un barreau au barreau qui le suit (Hérédité).
Alors :
On peut monter l'échelle. (la conclusion)
II- Énoncé :
Raisonnement par récurrence
Soit
une propriété définie sur
. Si :
La propriété est initialisée à partir du premier rang
, c'est-à-dire :
.
Et la propriété est héréditaire, c'est-à-dire :
.
Alors la propriété
est vraie pour tout
On commence par énoncer la propriété à démontrer, en précisant pour quels entiers naturels cette propriété est définie, notamment le premier rang.
Il est fortement conseillé de toujours noter la propriété à démontrer
, cela facilite grandement la rédaction et nous évite des ambiguités.
Un raisonnement par récurrence se rédige en trois étapes :
1-On vérifie
l'initialisation, c'est-à-dire que la propriété est vraie au premier rang (qui est souvent 0 ou 1).
2-On prouve
le caractère héréditaire de la propriété, on suppose que la propriété est vraie pour un entier
fixé et on démontre que la propriété est encore vraie au rang
.
Ici, on utilise toujours la propriété pour
pour montrer qu'elle est vraie aussi pour
Il est conseillé de mettre dans un coin le résultat au rang
à démontrer pour éviter des calculs fastidieux inutiles.
3-On conclut en invoquant le principe de récurrence.
Pour ceux qui veulent aller plus loin (supérieur), cela peut s'écrire :
Concrètement dans les exercices, c'est la partie en bleu qu'on démontre et on conclut par la partie en rouge.
III-Exemples :
Exemple 1 :
Exercice :
Montrer par récurrence que :
Puisqu'il s'agit d'un premier exemple, on va détailler (peut-être trop) en expliquant chaque étape. Nous exposerons ensuite une deuxième rédaction plus légère pour montrer comment bien rédiger un raisonnement par récurrence.
Résolution étape par étape bien détaillée aux fins d'explication :
Il faut montrer par récurrence que pour tout
On pose pour cela :
Et puisqu'il s'agit des entiers
appartenant à
, le premier rang est
car il est le premier élément dans l'ensemble
1-Initialisation : Pour
Donc la proposition
est vraie.
Remarques :
La somme
veut dire qu'on additionne les nombres de
à
. Donc pour le cas
, on additionne les nombres de
à
, ce qui implique que la somme vaut
et pas
.
On peut écrire les sommes en utilisant le symbole de la somme
qu'on exposera après dans le paragraphe suivant.
On n'écrit pas
car
n'est pas un nombre qu'on calcule et on
N'écrit
PAS .
est plutôt une proposition ("une phrase" mathématique) qui se lit : " La somme
est égale à
"
2-Hérédité : Soit
un entier naturel.
Supposons que
est vraie, et montrons que dans ce cas,
est vraie.
Pour pouvoir démontrer une propriété mathématique, il faut tout d'abord la connaître. Dans notre cas, il faut, avant de commencer, trouver ce qu'est l'expression de
.
En général, on remplace tout simplement
dans l'expression de
par
pour trouver l'expression de
On simplifie et on trouve :
On va montrer que
à partir de
Pour ne pas se perdre, on écrit dans un coin :
Hypothèse :
Résultat à prouver :
On sait que
car elle est la somme de
à
et le nombre qui précède
est
.
Donc :
Donc on a bien
est donc
est vraie
3- Conclusion :
On a vu que la propriété était vraie au rang 0 et qu'elle est héréditaire, donc elle est vraie
au rang 1, donc au rang 2...et de proche en proche elle est donc toujours vraie
Par récurrence, on obtient :
Rédaction de la résolution :
Montrons par récurrence que pour tout
Notons pour cela :
Initialisation : Pour
Hérédité : Soit
un entier naturel et supposons que
est vraie.
Hypothèse :
Résultat à prouver :
On a :
On en déduit que
est vraie.
On conclut par récurrence que :
Exemple 2 :
Exercice :
Montrer par récurrence que :
Montrons par récurrence que pour tout
On pose :
Initialisation : Pour
:
Donc
est vraie.
Hérédité : Soit
un entier naturel tel que
et supposons que
est vraie.
Montrons que
est vraie.
Hypothèse :
Résultat à prouver :
Or, puisque
On en déduit
et il s'ensuit que
est donc vraie.
On conclut par récurrence que :
Exemple 3 : Application aux suites
Prérequis : Les suites numériques
Exercice :
Soit une suite
avec
définie par :
Montrons par récurrence que
.
On pose
Initialisation : Pour
on a :
La proposition
est vraie.
Hérédité : Soit
un entier naturel et supposons que
est vraie.
Montrons que dans ce cas,
l'est aussi.
Hypothèse :
Résultat à prouver :
On a
Donc
Donc
Or, puisque
, on a :
Cela veut dire que
est vraie.
On conclut par récurrence que :
IV- Supplément : les symboles somme et produit :
1- Symbole
Le symbole mathématique
permet d'exprimer plus simplement des
sommes et donc des expressions mathématiques, par exemple, la somme
peut s'écrire :
Ce terme se lit
"somme pour allant de 0 à 10 de ".
Cela signifie que l'on fait prendre au nombre
toutes les valeurs entières entre 0 et 10 et qu'on fait la somme des nombres
:
On met la première valeur entière en bas du symbole, dans notre cas c'est 0.
On met la dernière valeur entière en haut du symbole sugma, ici c'est 10.
La lettre
est muette, elle ne sert qu'à compter et n'intervient pas dans le résultat final, on peut la remplacer par n'importe quelle autre variable
(on évite l'utilisation des lettres déjà utilisées dans l'exercice) :
Prenons la somme du premier exemple du paragraphe précédent, on pouvait écrire :
Autres exemples :
1-
2-
3-
Remarque : Dans l'exemple
1-, on ne pouvait pas débuter par
car le dénominateur ne peut pas être nul.
2- Symbole
Comme son homologue
pour les sommes, le symbole mathématique
permet d'exprimer plus simplement des
produits, par exemple, le produit
peut s'écrire :
Exemples :
Remarquer que le produit présenté précédemment :
3- Exercice d'application :
Énoncé :
Montrer que :
1-
2-
Solution :
1-Montrons par récurrence que
.
Notons
Il est conseillé d'écrire les termes avec sigma sous forme d'addition :
Initialisation : Pour
, on a :
Donc :
et
est vraie.
Hérédité :Soit
un entier de
, supposons que
est vraie et montrons que
est vraie (On évite l'utilisation de la lettre
pour l'hérédité car déjà utilisée comme variable muette de la somme).
Hypothèse :
Résultat à prouver :
On a :
Or, on a :
Donc :
Cela veut dire que
est vraie.
On conclut par récurrence que :
.
2-Montrons par récurrence que
On note
Écriture de la somme sous forme d'addition :
Initialisation : Pour
, on calcule :
Donc :
et
est vraie.
Hérédité :Soit
un entier de
, supposons que
est vraie et montrons que
est vraie.
Hypothèse :
Résultat à prouver :
On a :
Il s'ensuit que
est vraie.
Conclusion, par récurrence :
Merci à Panter pour avoir contribué à l'élaboration de cette fiche