Ah, la démonstration par récurrence ! Elle a fait pâlir plus d’un élève de lycée… Et pourtant, ce principe de démonstration est assez intuitif et, surtout, facile à appliquer, une fois bien compris. Reprenons donc depuis le début.
La démonstration par récurrence, ou le principe des dominos
Oublions un instant le formalisme mathématique et revenons à une dimension plus manuelle.
Imaginons un axe sur lequel seraient alignés une infinité de dominos, disposés verticalement. Numérotons ces dominos dans l’ordre : 0, 1, 2, 3, etc. L’objectif est de faire tomber tous les dominos.
Pour cela, il faut que deux conditions soient réunies :
- Les dominos doivent être placés suffisamment près les uns des autres, de sorte que si le domino numéro \(n\) tombe, alors le domino suivant (le numéro \(n+1\)) tombe également.
- Il faut faire tomber le domino numéro 0 (sinon il ne se passe rien du tout) !
Si ces deux conditions sont réunies, alors c’est gagné, tous les dominos tombent !
Intuitif, non ? Eh bien il s’agit exactement du principe de la démonstration par récurrence. Essayons de le comprendre en reformulant cet exemple des dominos en termes mathématiques.
La démonstration par récurrence sert à démontrer des propriétés qui portent sur les entiers naturels, c’est-à-dire des propriétés de la forme : Pour tout \(n \in \mathbb{N}\), blablabla. Dans notre exemple ci-dessus, la propriété à démontrer serait : Pour tout \(n \in \mathbb{N}\), le domino numéro \(n\) tombe.
On note H(\(n\)) une telle propriété au rang \(n\). Dans notre exemple, on aurait donc :
H(\(n\)) : Le domino numéro \(n\) tombe.
La démonstration par récurrence consiste :
- D’abord, à vérifier que la propriété est vraie au rang 0 (i.e. on vérifie que H(0) est vraie). Dans notre exemple des dominos, cela revient à vérifier que le premier domino (le domino numéro 0) tombe. Cette étape s’appelle l’initialisation.
- Ensuite, à vérifier que si la propriété est vraie à un rang \(n\), alors elle sera aussi vraie au rang \(n+1\) (i.e. on vérifie que si H(\(n\)) est vraie, alors H(\(n+1\)) est aussi vraie). Dans notre exemple, cela revient à constater que, si le domino numéro \(n\) tombe, comme la distance entre les dominos est suffisamment petite, alors le domino numéro \(n+1\) tombe également. Cette étape s’appelle l’hérédité.
Si ces deux étapes sont vérifiées, alors la propriété sera vraie pour tous les entiers naturels (on aura démontré que pour tout \(n \in \mathbb{N}\), H(\(n\)) est vraie). Dans notre exemple, cela revient à dire que tous les dominos tombent (car pour tout \(n \in \mathbb{N}\), le domino numéro \(n\) tombe). C’est la conclusion du raisonnement par récurrence.
Méthodologie : rédiger efficacement une démonstration par récurrence
Il faut penser à tenter une démonstration par récurrence lorsqu’on est en présence d’une propriété qui se propage de proche en proche sur les entiers naturels (comme la chute de nos dominos). Toutefois, il n’est pas toujours facile d’identifier de telles propriétés. Il faut donc toujours avoir en tête que l’on dispose de la démonstration par récurrence dans notre boite à outils mathématiques et envisager de l’utiliser si l’on nous demande de démontrer une propriété portant sur les entiers naturels qui ne nous semble pas facile à prouver de manière directe.
Une fois identifiée une démonstration à faire par récurrence, il faut :
- Énoncer clairement la propriété H(\(n\)) pour tout \(n \in \mathbb{N}\).
- Faire l’initialisation : on démontre H(0).
- Démontrer l’hérédité. Soit \(n \in \mathbb{N}\), on suppose que H(\(n\)) est vraie, et on en déduit que H(\(n+1\)) est vraie.
- Conclure avec une phrase du type : D’après le principe de récurrence, la propriété est vraie pour tout \(n \in \mathbb{N}\).
Exercices
Exercice 1 sur la démonstration par récurrence classique
On définit la suite \((u_n)\) par :
\(\begin{cases} u_{0}=3 \\ \forall n \in \mathbb{N}, u_{n+1}=4u_{n} \end{cases}\)
Démontrer que : \(\forall n \in \mathbb{N}, u_{n}=4^n \times 3 \)
Correction de l’exercice 1
On pose pour tout \(n \in \mathbb{N} \) H(\(n\) : “\(u_{n}=4^n \times 3 \)”
Initialisation : pour \(n=0\)
on a \(u_{0}=3=4^{0} \times 3\)
Donc H(0) est vérifiée
Hérédité : Soit \(n \in \mathbb{N} \). Supposons que H(\(n\)) est vraie. Montrons alors que : \(u_{n+1}=4^{n+1} \times 3 \)
On peut écrire :
\(u_{n+1}=4\times u_{n}\), d’où d’après l’hypothèse de récurrence :
\(u_{n+1}=4\times 4^n \times 3\), ie.
\(u_{n+1}=4^{n+1} \times 3\)
Donc H(\(n+1\)) est vraie.
Conclusion : Par principe de récurrence, on a : \(\forall n \in \mathbb{N}, u_{n}=4^n \times 3 \)
Exercice 2 sur une démonstration par récurrence un peu plus poussée
Démontrer que pour tout \(n \in \mathbb{N}, 2^{2n}+2\) est un entier divisible par 3.
Rappel sur les diviseurs
Un entier naturel \(b\) est un diviseur de l’entier naturel \(a\) lorsque le reste de la division euclidienne de \(a\) par \(b\) est égal à 0. Donc : \( \exists q \in \mathbb{N}, \ a = b.q \)
Correction de l’exercice 2
On pose pour tout \(n \in \mathbb{N} \), H(\(n\)) : “\(2^{2n}+2\) est un entier divisible par 3”
Initialisation : pour \(n=0\)
On a \(2^{2} \times 0+2 =1+2=3\), or \(3=3 \times 1\), donc en posant \(q=1\)
\(\exists q \in \mathbb{N}\), \(3 = 3.q\), donc par définition, 3 est bien divisible par 3.
Donc \(2^{2 \times 0}+2\) est bien un entier divisible par 3
Donc H(0) est vérifiée.
Hérédité : Soit \(n \in \mathbb{N} \). Supposons que H(\(n\)) est vraie. Montrons alors que : \(2^{2(n+1)}+2\) est un entier divisible par 3
On a :
\(2^{2(n+1)}+2=2^{2n+2)}+2 \)
\(\qquad \qquad=2^{2n} \times 2^{2}+2 \)
\(\qquad \qquad=2^{2n} \times 4+2\)
\(\qquad \qquad=2^{2n} \times 3+2^{2n}+2\)
\(\qquad \qquad=(2^{2n} \times 3)+(2^{2n}+2)\)
Or en posant \(l=2^{2n}\), on peut écrire :
\(\exists l \in \mathbb{N}, 2^{2n} \times 3 = 3.l\), donc par définition, \(2^{2n} \times 3\) est un entier divisible par 3
Comme en outre, d’après l’hypothèse de récurrence, \(2^{2n}+2\) est un entier divisible par 3, alors par définition :
\(\exists k \in \mathbb{N}, 2^{2n}+2 = 3.k\), d’où :
\(2^{2(n+1)}+2=3l+3k \), donc :
\(\qquad \qquad=3(l+k) \), et en posant \(m=l+k\), on peut écrire :
\(\exists m \in \mathbb{N}, 2^{2(n+1)}+2= 3.m\)
Donc par définition, \(2^{2(n+1)}+2\) est un entier divisible par 3.
Ainsi, H(\(n+1\)) est vérifiée.
Conclusion : Par principe de récurrence, on a, pour tout \(n \in \mathbb{N}\), \(2^{2n}+2\) qui est un entier divisible par 3
Pour aller un peu plus loin : la récurrence “à partir d’un certain rang”
Si tu as bien compris les deux premiers paragraphes de cet article et si tu as réussi à faire les deux exercices du paragraphe ci-dessus, tu es armé·e pour répondre à l’essentiel des questions que l’on pourrait te poser autour de la démonstration par récurrence.
Cependant, ce principe de démonstration peut être légèrement adapté pour démontrer des propriétés non plus sur l’ensemble des entiers naturels, mais à partir d’un certain rang seulement. Mais le principe est exactement le même, comme tu vas vite le comprendre en reprenant notre exemple des dominos.
Imaginons en effet que l’on ne souhaite plus faire tomber tous les dominos, mais seulement les dominos dont les numéros sont supérieurs ou égaux à 11. Facile, non ? Il suffit que :
- Les dominos dont les numéros sont supérieurs ou égaux à 11 soient placés suffisamment près les uns des autres, de sorte que si le domino numéro n tombe, alors le domino suivant (le numéro n+1) tombe également, pour n ≥ 11.
- On fasse tomber le domino numéro 11 (et non plus le domino numéro 0) !
Si ces deux conditions sont réunies, alors c’est gagné : tous les dominos dont les numéros sont supérieurs ou égaux à 11 tombent !
Si l’on formalise ceci mathématiquement on obtient la méthodologie suivante.
Soit \(n_{0} \in \mathbb{Z}\) et une propriété à montrer sur l’ensemble des entiers compris entre le premier terme \(n_{0}\) et \({\displaystyle +\infty }\) (on note cet ensemble : \([\
