Le principe de récurrence est l'une des méthodes de démonstration les plus importantes de toutes les mathématiques. Il permet de prouver qu'une propriété est vraie pour tous les entiers naturels, en transformant un problème comportant une infinité de cas en un raisonnement fini, rigoureux et maîtrisable.
L'idée centrale est simple : si une propriété est vraie au départ et si, chaque fois qu'elle est vraie pour un certain entier naturel, elle l'est aussi pour le suivant, alors elle est vraie pour tous les entiers naturels.
Sommaire
- Intuition du principe de récurrence
- Énoncé du principe de récurrence
- Initialisation et hérédité
- Pourquoi la récurrence fonctionne
- Récurrence à partir d'un rang arbitraire
- Récurrence et ensembles inductifs
- Exemple 1 : somme des premiers entiers naturels
- Exemple 2 : une inégalité exponentielle
- Principe du bon ordre
- Équivalence entre récurrence et bon ordre
- Récurrence forte
- Erreurs fréquentes dans les démonstrations par récurrence
- Récurrence et définitions récursives
- Conclusion
Intuition du principe de récurrence
Le principe de récurrence est souvent illustré par l'image des dominos.
Imaginons une rangée infinie de dominos. Pour s'assurer que tous tombent, il n'est pas nécessaire de vérifier chaque domino un à un. Il suffit d'établir deux faits :
- le premier domino tombe ;
- chaque domino, en tombant, fait tomber le suivant.
Si ces deux conditions sont remplies, alors tous les dominos de la rangée tomberont.
En mathématiques, il se passe quelque chose d'analogue. Pour démontrer qu'une propriété \(P(n)\) est vraie pour tout entier naturel \(n\), on vérifie qu'elle est vraie pour la première valeur et on montre que sa validité en un rang quelconque implique sa validité au rang suivant.
Énoncé du principe de récurrence
Soit \(P(n)\) une propriété dépendant d'un entier naturel \(n\). Le principe de récurrence affirme que, si les deux conditions suivantes sont satisfaites :
\[ P(1) \text{ est vraie} \]
et
\[ P(n) \Rightarrow P(n+1) \quad \text{pour tout } n \geq 1, \]
alors :
\[ P(n) \text{ est vraie pour tout } n\in\mathbb{N}, \ n\geq 1. \]
Si l'on adopte la convention selon laquelle les entiers naturels commencent à \(0\), la base de la récurrence sera \(P(0)\) et l'hérédité sera :
\[ P(n) \Rightarrow P(n+1) \quad \text{pour tout } n\geq 0. \]
Initialisation et hérédité
Une démonstration par récurrence se déroule en deux étapes fondamentales.
1. Initialisation
On démontre que la propriété est vraie pour la première valeur considérée, le plus souvent \(n=1\) ou \(n=0\).
Cette vérification est indispensable : sans point de départ, la chaîne de récurrence ne peut pas s'enclencher.
2. Hérédité
On suppose que la propriété est vraie pour un certain entier naturel \(n\). Cette supposition s'appelle l'hypothèse de récurrence.
À partir d'elle, on démontre que la propriété est vraie pour \(n+1\).
En écriture symbolique :
\[ P(n)\Rightarrow P(n+1). \]
Le point essentiel est qu'on ne suppose pas que la propriété est vraie pour tous les entiers naturels. On démontre une implication : si la propriété est valide en un certain maillon de la chaîne, alors elle l'est aussi au maillon suivant.
Pourquoi la récurrence fonctionne
Le principe de récurrence fonctionne parce que les entiers naturels sont construits de façon ordonnée et successive :
\[ 1,2,3,4,\dots \]
ou, si l'on part de \(0\) :
\[ 0,1,2,3,\dots \]
Une fois le premier cas établi, l'hérédité permet de passer du premier au deuxième, du deuxième au troisième, du troisième au quatrième, et ainsi de suite.
On engendre ainsi une chaîne infinie d'implications :
\[ P(1)\Rightarrow P(2)\Rightarrow P(3)\Rightarrow P(4)\Rightarrow \dots \]
Toute la puissance de la récurrence tient précisément à cela : un raisonnement fini parvient à contrôler une infinité de cas en exploitant la structure même des entiers naturels.
Récurrence à partir d'un rang arbitraire
Il n'est pas nécessaire que la chaîne de récurrence parte toujours de \(n=1\) ou de \(n=0\). Dans de nombreuses situations, une propriété ne devient vraie qu'à partir d'un certain entier \(n_0\).
Dans ce cas, le principe de récurrence s'énonce ainsi. Si :
\[ P(n_0) \text{ est vraie} \]
et
\[ P(n)\Rightarrow P(n+1) \quad \text{pour tout } n\geq n_0, \]
alors :
\[ P(n) \text{ est vraie pour tout } n\geq n_0. \]
Par exemple, démontrons que :
\[ 2^n>n^2 \]
pour tout \(n\geq 5\).
Initialisation
Pour \(n=5\), on a :
\[ 2^5=32 \]
et
\[ 5^2=25. \]
Donc :
\[ 2^5>5^2. \]
Hérédité
Supposons que, pour un certain \(n\geq 5\), on ait :
\[ 2^n>n^2. \]
Montrons que :
\[ 2^{n+1}>(n+1)^2. \]
Comme :
\[ 2^{n+1}=2\cdot 2^n, \]
en utilisant l'hypothèse de récurrence, on obtient :
\[ 2^{n+1}=2\cdot 2^n>2n^2. \]
Observons maintenant que, pour tout \(n\geq 5\),
\[ 2n^2>(n+1)^2. \]
En effet :
\[ 2n^2-(n+1)^2 = n^2-2n-1. \]
Pour \(n\geq 5\), on a :
\[ n^2-2n-1=(n-1)^2-2\geq 4^2-2=14>0. \]
Donc :
\[ 2n^2>(n+1)^2. \]
En combinant les deux inégalités, on obtient :
\[ 2^{n+1}>2n^2>(n+1)^2. \]
Par conséquent :
\[ 2^{n+1}>(n+1)^2. \]
L'hérédité est démontrée. Par le principe de récurrence à partir de \(n_0=5\), on conclut que :
\[ 2^n>n^2 \]
pour tout \(n\geq 5\).
La logique est inchangée : la chaîne d'implications démarre simplement à un rang différent.
Récurrence et ensembles inductifs
Le principe de récurrence peut également s'exprimer dans le langage des ensembles.
Un sous-ensemble \(A\subseteq\mathbb{N}\) est dit inductif s'il satisfait deux conditions :
\[ 1\in A \]
et
\[ n\in A\Rightarrow n+1\in A. \]
Autrement dit, \(A\) contient le premier entier naturel et, avec chaque entier, son successeur.
Le principe de récurrence affirme alors que :
\[ \text{si } A\subseteq\mathbb{N} \text{ est inductif, alors } A=\mathbb{N}. \]
Cette formulation met en lumière un fait fondamental : la récurrence n'est pas seulement une technique pour résoudre des exercices, c'est une propriété structurelle de l'ensemble des entiers naturels.
Exemple 1 : somme des premiers entiers naturels
Démontrons par récurrence que, pour tout \(n\geq 1\),
\[ 1+2+3+\dots+n=\frac{n(n+1)}{2}. \]
Initialisation
Pour \(n=1\), le membre gauche vaut :
\[ 1. \]
Le membre droit vaut :
\[ \frac{1(1+1)}{2}=\frac{2}{2}=1. \]
La formule est donc vraie pour \(n=1\).
Hérédité
Supposons la formule vraie pour un certain \(n\geq 1\), c'est-à-dire supposons :
\[ 1+2+3+\dots+n=\frac{n(n+1)}{2}. \]
Montrons qu'elle est alors vraie au rang \(n+1\) :
\[ 1+2+3+\dots+n+(n+1)=\frac{(n+1)(n+2)}{2}. \]
Partons du membre gauche :
\[ 1+2+3+\dots+n+(n+1). \]
Par hypothèse de récurrence, on peut remplacer la somme \(1+2+\dots+n\) par \(\frac{n(n+1)}{2}\) :
\[ 1+2+\dots+n+(n+1)=\frac{n(n+1)}{2}+(n+1). \]
En factorisant par \(n+1\) :
\[ \frac{n(n+1)}{2}+(n+1) = (n+1)\left(\frac{n}{2}+1\right). \]
Comme :
\[ \frac{n}{2}+1=\frac{n+2}{2}, \]
on obtient :
\[ (n+1)\left(\frac{n}{2}+1\right) = \frac{(n+1)(n+2)}{2}. \]
Donc :
\[ 1+2+\dots+n+(n+1)=\frac{(n+1)(n+2)}{2}. \]
La propriété est ainsi vraie au rang \(n+1\). Par le principe de récurrence, la formule est valide pour tout \(n\geq 1\).
Exemple 2 : une inégalité exponentielle
Démontrons que, pour tout \(n\in\mathbb{N}\) avec \(n\geq 0\),
\[ 2^n\geq n+1. \]
Initialisation
Pour \(n=0\), on a :
\[ 2^0=1 \]
et
\[ 0+1=1. \]
Donc :
\[ 2^0\geq 0+1. \]
La propriété est vraie pour \(n=0\).
Hérédité
Supposons que, pour un certain \(n\geq 0\), on ait :
\[ 2^n\geq n+1. \]
Montrons que :
\[ 2^{n+1}\geq n+2. \]
On remarque que :
\[ 2^{n+1}=2\cdot 2^n. \]
En utilisant l'hypothèse de récurrence :
\[ 2\cdot 2^n\geq 2(n+1). \]
Donc :
\[ 2^{n+1}\geq 2n+2. \]
Puisque \(n\geq 0\), on a :
\[ 2n+2\geq n+2. \]
Par conséquent :
\[ 2^{n+1}\geq n+2. \]
La propriété est donc vraie au rang \(n+1\). Par récurrence :
\[ 2^n\geq n+1 \]
pour tout \(n\geq 0\).
Principe du bon ordre
Le principe du bon ordre affirme que tout sous-ensemble non vide de \(\mathbb{N}\) possède un plus petit élément.
En symboles :
\[ A\subseteq\mathbb{N},\quad A\neq\varnothing \quad\Longrightarrow\quad \exists m\in A \text{ tel que } m\leq a \text{ pour tout } a\in A. \]
L'élément \(m\) s'appelle le minimum de \(A\).
Attention : le minimum n'est pas simplement un élément petit. C'est un élément de l'ensemble qui est inférieur ou égal à tous les autres éléments de cet ensemble.
Par exemple, si :
\[ A=\{5,8,13,21\}, \]
alors :
\[ \min A=5. \]
Si en revanche :
\[ B=\{n\in\mathbb{N}\mid n\geq 10\}, \]
alors :
\[ \min B=10. \]
Le principe du bon ordre est une propriété caractéristique des entiers naturels. Il ne s'applique pas, par exemple, à tous les sous-ensembles non vides de \(\mathbb{Z}\). En effet, l'ensemble :
\[ \mathbb{Z}=\{\dots,-3,-2,-1,0,1,2,3,\dots\} \]
n'admet pas de minimum.
Équivalence entre récurrence et bon ordre
Le principe de récurrence et le principe du bon ordre sont équivalents : en admettant l'un, on peut démontrer l'autre.
Cette équivalence est importante car elle montre que la récurrence n'est pas un simple artifice technique, mais une conséquence profonde de la structure ordonnée des entiers naturels.
Du bon ordre au principe de récurrence
Supposons le principe du bon ordre admis. Nous voulons en déduire le principe de récurrence.
Soit \(P(n)\) une propriété des entiers naturels. Supposons que :
\[ P(1) \text{ est vraie} \]
et que :
\[ P(n)\Rightarrow P(n+1) \quad \text{pour tout } n\geq 1. \]
Montrons que \(P(n)\) est vraie pour tout \(n\geq 1\).
Raisonnons par l'absurde. Supposons qu'il existe au moins un entier naturel pour lequel \(P\) est fausse. Considérons l'ensemble des contre-exemples :
\[ A=\{n\in\mathbb{N}\mid P(n)\text{ est fausse}\}. \]
Par hypothèse, \(A\neq\varnothing\). Donc, par le principe du bon ordre, \(A\) possède un plus petit élément, que l'on note \(m\).
Puisque \(P(1)\) est vraie, l'entier \(1\) n'appartient pas à \(A\). Donc \(m\neq 1\), ce qui donne \(m>1\).
Alors \(m-1\) est un entier naturel strictement inférieur à \(m\). Comme \(m\) est le plus petit élément de \(A\), le nombre \(m-1\) ne peut pas appartenir à \(A\).
Donc \(P(m-1)\) est vraie.
Or, par l'hérédité :
\[ P(m-1)\Rightarrow P(m). \]
Il s'ensuit que \(P(m)\) est vraie.
Cela est impossible, car \(m\in A\) et \(P(m)\) devrait donc être fausse.
On aboutit à une contradiction. L'ensemble des contre-exemples est donc vide :
\[ A=\varnothing. \]
Ainsi \(P(n)\) est vraie pour tout \(n\geq 1\). Le principe de récurrence est démontré.
Du principe de récurrence au bon ordre
Supposons maintenant le principe de récurrence admis. Nous voulons en déduire le principe du bon ordre.
Soit \(A\subseteq\mathbb{N}\) un sous-ensemble non vide. Montrons que \(A\) possède un plus petit élément.
Raisonnons par l'absurde. Supposons que \(A\) n'ait pas de plus petit élément.
Si \(1\in A\), alors \(1\) serait automatiquement le minimum de \(A\), car aucun entier naturel positif n'est inférieur à \(1\). Mais par hypothèse \(A\) n'a pas de minimum. Donc :
\[ 1\notin A. \]
Considérons la propriété :
\[ P(n): \quad 1,2,\dots,n \notin A. \]
Autrement dit, \(P(n)\) affirme qu'aucun des \(n\) premiers entiers naturels n'appartient à \(A\).
Initialisation
On a déjà établi que :
\[ 1\notin A. \]
Donc \(P(1)\) est vraie.
Hérédité
Supposons \(P(n)\) vraie, c'est-à-dire supposons que :
\[ 1,2,\dots,n \notin A. \]
Montrons que :
\[ 1,2,\dots,n,n+1 \notin A. \]
Par hypothèse de récurrence, \(1,2,\dots,n\) n'appartiennent pas à \(A\). Il reste à montrer que \(n+1\notin A\).
Si l'on avait :
\[ n+1\in A, \]
alors \(n+1\) serait le plus petit élément de \(A\), puisqu'aucun des entiers naturels précédents n'appartient à \(A\).
Cela contredirait l'hypothèse que \(A\) n'a pas de minimum.
Donc :
\[ n+1\notin A. \]
L'hérédité est démontrée.
Par le principe de récurrence, \(P(n)\) est vraie pour tout \(n\geq 1\). Aucun entier naturel n'appartient donc à \(A\), c'est-à-dire :
\[ A=\varnothing. \]
Cela est impossible, puisqu'on avait supposé \(A\neq\varnothing\).
La contradiction montre que \(A\) doit posséder un plus petit élément. Le principe du bon ordre est démontré.
Récurrence forte
Il existe une variante du principe de récurrence appelée récurrence forte.
Dans la récurrence ordinaire, pour démontrer \(P(n+1)\), on suppose seulement \(P(n)\).
Dans la récurrence forte, en revanche, pour démontrer \(P(n+1)\), on suppose vraies toutes les propriétés précédentes :
\[ P(1),P(2),\dots,P(n). \]
L'énoncé est le suivant. Si :
\[ P(1) \text{ est vraie} \]
et, pour tout \(n\geq 1\),
\[ P(1)\land P(2)\land \dots \land P(n) \Rightarrow P(n+1), \]
alors :
\[ P(n) \text{ est vraie pour tout } n\geq 1. \]
La récurrence forte n'est pas logiquement plus puissante que la récurrence ordinaire : les deux formes sont équivalentes. Cependant, dans de nombreuses démonstrations, la récurrence forte est plus naturelle et plus commode à utiliser.
Exemple 1 : décomposition en facteurs premiers
Un exemple classique d'application de la récurrence forte est la démonstration du fait que tout entier naturel supérieur à \(1\) est premier ou s'écrit comme produit de nombres premiers.
Soit \(n>1\). Si \(n\) est premier, il n'y a rien à démontrer.
Si \(n\) n'est pas premier, alors il existe deux entiers \(a\) et \(b\), tous deux strictement compris entre \(1\) et \(n\), tels que :
\[ n=ab. \]
Comme \(a<n\) et \(b<n\), l'hypothèse de récurrence forte permet de supposer que \(a\) et \(b\) sont premiers ou produits de nombres premiers.
Par conséquent, \(n=ab\) est lui aussi produit de nombres premiers.
Cet exemple montre pourquoi, dans certains contextes, il est utile de disposer non seulement du rang immédiatement précédent, mais de tous les rangs antérieurs.
Exemple 2 : la suite de Fibonacci
La suite de Fibonacci est définie par :
\[ F_1=1,\quad F_2=1,\quad F_n=F_{n-1}+F_{n-2} \quad \text{pour tout } n\geq 3. \]
Démontrons par récurrence forte que, pour tout \(n\geq 1\),
\[ F_n<2^n. \]
Initialisations
Pour \(n=1\) :
\[ F_1=1<2=2^1. \]
Pour \(n=2\) :
\[ F_2=1<4=2^2. \]
Deux initialisations sont nécessaires car la relation de récurrence fait intervenir les deux termes précédents.
Hérédité
Soit \(n\geq 3\). Supposons, par hypothèse de récurrence forte, que l'inégalité soit vraie pour tous les indices inférieurs à \(n\). En particulier :
\[ F_{n-1}<2^{n-1} \qquad \text{et} \qquad F_{n-2}<2^{n-2}. \]
Alors :
\[ F_n=F_{n-1}+F_{n-2} < 2^{n-1}+2^{n-2}. \]
Comme :
\[ 2^{n-1}+2^{n-2} = 2^{n-2}(2+1) = 3\cdot 2^{n-2}, \]
et puisque \(3<4\), on obtient :
\[ 3\cdot 2^{n-2} < 4\cdot 2^{n-2} = 2^2\cdot 2^{n-2} = 2^n. \]
Donc :
\[ F_n<2^n. \]
Par le principe de récurrence forte, \(F_n<2^n\) pour tout \(n\geq 1\).
Cet exemple illustre bien pourquoi la récurrence forte est naturelle ici : la relation \(F_n=F_{n-1}+F_{n-2}\) fait intervenir les deux termes précédents et non pas seulement le précédent immédiat. Recourir directement à la récurrence forte rend ainsi le raisonnement plus fluide.
Erreurs fréquentes dans les démonstrations par récurrence
1. Omettre l'initialisation
Sans initialisation, l'hérédité ne suffit pas. Démontrer seulement :
\[ P(n)\Rightarrow P(n+1) \]
ne garantit pas que la propriété soit vraie pour un seul entier naturel.
C'est comme affirmer que chaque domino fait tomber le suivant, sans jamais faire tomber le premier.
2. Mal utiliser l'hypothèse de récurrence
L'hypothèse de récurrence doit être utilisée exactement dans la forme où elle a été posée.
Si l'on veut démontrer \(P(n+1)\), il faut partir de P(n) et la transformer correctement au rang suivant.
3. Démontrer une implication incomplète
L'hérédité doit être valide pour toute valeur de \(n\) dans le domaine considéré.
Si le raisonnement ne fonctionne que pour certaines valeurs de \(n\), la démonstration est invalide.
Le paradoxe des chevaux
Un exemple célèbre de fausse démonstration par récurrence est le paradoxe des chevaux.
On cherche à établir l'affirmation suivante :
\[ P(n): \quad \text{dans tout ensemble de } n \text{ chevaux, tous les chevaux ont la même couleur.} \]
Pour \(n=1\), la propriété est vraie : dans un ensemble réduit à un seul cheval, tous les chevaux ont évidemment la même couleur.
Considérons un ensemble de \(n+1\) chevaux :
\[ \{c_1,c_2,\dots,c_n,c_{n+1}\}. \]
Les \(n\) premiers chevaux :
\[ \{c_1,c_2,\dots,c_n\} \]
ont tous la même couleur, par hypothèse de récurrence. Les \(n\) derniers :
\[ \{c_2,c_3,\dots,c_{n+1}\} \]
ont également tous la même couleur, toujours par hypothèse de récurrence.
Les deux sous-ensembles se chevauchant, il semblerait s'ensuivre que les \(n+1\) chevaux ont tous la même couleur.
L'erreur se situe dans le passage de \(n=1\) à \(n=2\). Dans ce cas, les deux sous-ensembles sont :
\[ \{c_1\} \qquad \text{et} \qquad \{c_2\}, \]
et ils n'ont aucun élément en commun. Il n'existe donc aucun cheval commun permettant de relier la couleur du premier à celle du second.
L'hérédité n'est pas valide pour toutes les valeurs de \(n\), mais seulement pour \(n\geq 2\). La chaîne de récurrence se brise précisément dans le passage de \(P(1)\) à \(P(2)\).
4. Confondre vérification numérique et démonstration
Vérifier une formule pour \(n=1\), \(n=2\), \(n=3\) et \(n=4\) peut laisser penser qu'elle est vraie, mais ne constitue pas une démonstration.
La récurrence ne consiste pas à tester de nombreux cas particuliers, mais à établir un mécanisme général de passage du rang \(n\) au rang \(n+1\).
Récurrence et définitions récursives
Le principe de récurrence est étroitement lié aux définitions récursives.
De nombreux objets mathématiques sont définis en précisant :
- une ou plusieurs valeurs initiales ;
- une règle permettant de construire les termes suivants.
Par exemple, la factorielle est définie par :
\[ 0!=1 \]
et
\[ (n+1)!=(n+1)n!. \]
La récursion construit les objets pas à pas, tandis que la récurrence permet de démontrer des propriétés valables pour tous les objets ainsi construits.
Récursion et récurrence sont donc deux aspects complémentaires de la structure des entiers naturels : la récursion définit, la récurrence démontre.
Conclusion
Le principe de récurrence est bien plus qu'une technique pour démontrer des formules. Il exprime une propriété fondamentale des entiers naturels : chaque entier naturel est accessible en partant du premier et en appliquant successivement l'opération du successeur.
Sa force réside dans la transformation d'une assertion portant sur une infinité de cas en deux vérifications finies :
- une initialisation ;
- une règle de propagation du rang \(n\) au rang \(n+1\).
De plus, l'équivalence avec le principe du bon ordre montre que la récurrence est profondément ancrée dans la structure ordonnée de \(\mathbb{N}\).
C'est pourquoi le principe de récurrence occupe une place centrale en algèbre, en théorie des nombres, en logique, en combinatoire, en informatique théorique et dans de nombreux autres domaines des mathématiques.
En définitive, la récurrence mathématique montre comment il est possible de maîtriser l'infini par un raisonnement fini, à condition que la structure logique soit construite avec rigueur.