Licence CC BY

Le principe de récurrence

Dans cette partie, nous introduisons le principe de récurrence, d’abord au travers de l’exemple de la somme des entiers de 0 à nn puis de façon plus générale. L’objectif est de vous faire assimiler les concepts derrière le raisonnement par récurrence afin que vous soyez en mesure de l’appliquer dans la suite du tutoriel.

Le contenu comprend un certain nombre de formules mathématiques. N’ayez crainte, il n’y a rien de compliqué derrière tout ça. Nous utilisons simplement ce formalisme pour rendre le propos clair (contrairement au français, le langage mathématique n’est pas ambigu) et vous permettre de vous familiariser avec ces notations courantes.

À ce titre, nous formulons d’abord l’idée en français puis en donnons l’expression dans le langage mathématique en expliquant tous les symboles utilisés.

Revenons à notre somme

Formulons le problème

Non seulement Gauss a donné le bon résultat pour la somme des entiers de 1 à 100, mais la façon dont il s’y est pris semble lui fournir une formule générique, qu’on obtient intuitivement en remplaçant 100 par nn :

1+2+3++n=n(n+1)2.1 + 2 + 3 + \ldots + n = \frac{n(n+1)}{2}.

Notre objectif est de démontrer que cette identité est vraie pour tout entier naturel nn. Avant d’avancer, remarquons que cette écriture n’est pas très claire. En effet, pour n=5n = 5, on conclut facilement que la partie de gauche est égale à 1+2+3+4+51 + 2 + 3 + 4 + 5. Mais qu’en est-il pour n=2n = 2 ? On se doute qu’il faut se débarrasser du 3 pour obtenir 1+21 + 2, mais se douter de quelque chose n’est pas suffisant en Mathématiques. C’est pour cela que nous opterons pour une écriture moins directe mais clairement définie pour tout entier naturel nn :

k=0nk.\sum_{k=0}^n k.

Ce qui signifie littéralement « la somme des entiers kk compris entre 0 inclus et nn inclus ». Le symbole étrange est la lettre majuscule grecque sigma (σ\sigma en minuscule).

Nous avons donc notre identité désormais clairement définie. Pour la désigner plus facilement, donnons lui un nom :

PnP_n : « k=0nk=n(n+1)2\sum_{k=0}^n k = \frac{n(n+1)}{2} ».

En Mathématiques, on dit que PnP_n est une proposition, c’est-à-dire un énoncé (ici une égalité) pouvant être soit vrai soit faux. L’ensemble des PnP_n forme ce qu’on appelle un prédicat (noté PP), c’est-à-dire un énoncé logique paramétré par une variable (ici nn). Comme cette dernière peut valoir n’importe quel entier naturel, on dit que PP est défini sur l’ensemble des entiers naturels.1 Parce qu’on peut numéroter les éléments de cet ensemble, c’est-à-dire définir le successeur d’un élément, on obtient une suite de propositions :

(P0,P1,P2,).(P_0, P_1, P_2, \ldots).

Comme pour les suites, les entiers pour lesquels est défini le prédicat sont appelés les rangs ou les indices, et pour désigner le prédicat à un rang particulier, on met généralement ce dernier en indice, parfois entre parenthèses :

P0P_0 : « k=00k=0(0+1)2\sum_{k=0}^0 k = \frac{0(0+1)}{2} »

P(1)P(1) : « k=01k=1(1+1)2\sum_{k=0}^1 k = \frac{1(1+1)}{2} »

P2P_2 : « k=02k=2(2+1)2\sum_{k=0}^2 k = \frac{2(2+1)}{2} »

Bien. Prenez le temps de digérer toutes ces notations et définitions. Ne vous cassez toutefois pas trop la tête avec ces termes et retenez surtout que PnP_n désigne notre énoncé logique (notre égalité) pour nn un entier naturel fixé. Dans la suite, nous nous attaquons à une question récurrente (ahah) en Mathématiques :

Peut-on démontrer PP ? Autrement dit, peut-on démontrer que la proposition PnP_n est vraie, quel que soit nn (entier naturel) ?

Démontrons notre prédicat

Comme il existe une infinité d’entiers naturels, on ne peut définitivement pas vérifier chaque PnP_n individuellement, même avec un ordinateur. Notons néanmoins que le faire pour les premiers entiers naturels aide à se familiariser avec le problème (comme ci-dessus, où nous avons explicitement écrit les propositions P0P_0, P1P_1 et P2P_2 ; on remarquera d’ailleurs qu’elles sont vraies).

Au lieu de cela, et c’est un réflexe important à acquérir, remarquons que Pn+1P_{n+1} semble découler de PnP_n. En effet, nous avons :

{k=0n+1k=(n+1)+k=0nk(n+1)(n+2)2=(n+1)n+(n+1)22=(n+1)+n(n+1)2.\left\{ \begin{aligned} \sum_{k=0}^{n+1} k &= (n+1) + \sum_{k=0}^n k \\ \frac{(n+1)(n+2)}{2} &= \frac{(n+1)n + (n+1)2}{2} = (n+1) + \frac{n(n+1)}{2} \end{aligned}\right..

La grande accolade ici signifie simplement « et ». En bidouillant les termes de Pn+1P_{n+1}, on obtient ceux de PnP_n et peut alors démontrer que si PnP_n est vraie, alors Pn+1P_{n+1} est vraie. On note cela PnPn+1P_n \Rightarrow P_{n+1} et prononce « PnP_n implique Pn+1P_{n+1} ». L’implication se prouve de cette manière :

Pnk=0nk=n(n+1)2(n+1)+k=0nk=(n+1)+n(n+1)2k=0n+1k=(n+1)+n(n+1)2k=0n+1k=2(n+1)+n(n+1)2k=0n+1k=(n+1)(n+2)2Pn+1.\begin{aligned} P_n &\Rightarrow \sum_{k=0}^n k = \frac{n(n+1)}{2} \\ &\Rightarrow (n+1) + \sum_{k=0}^n k = (n+1) + \frac{n(n+1)}{2} \\ &\Rightarrow \sum_{k=0}^{n+1} k = (n+1) + \frac{n(n+1)}{2} \\ &\Rightarrow \sum_{k=0}^{n+1} k = \frac{2(n+1) + n(n+1)}{2} \\ &\Rightarrow \sum_{k=0}^{n+1} k = \frac{(n+1)(n+2)}{2} \\ &\Rightarrow P_{n+1}. \end{aligned}

Donc PnPn+1P_n \Rightarrow P_{n+1}. Mais vous remarquerez que nous avons jusqu’ici considéré un nn quelconque : nous n’avons supposé rien d’autre que sa nature d’entier naturel. Autrement dit, cette implication est valable pour tout entier naturel nn !

Et c’est une aubaine puisqu’on peut en quelque sorte la chaîner à l’infini :

P0P1P2P_0 \Rightarrow P_1 \Rightarrow P_2 \Rightarrow \ldots

Comme la notation \ldots n’est pas définie en Mathématiques, on préfère écrire :

nN,PnPn+1.\forall n \in \mathbb N, P_n \Rightarrow P_{n+1}.

Où :

  • \forall signifie « pour tout » ;
  • \in veut dire « appartient » ;
  • N\mathbb N est la notation de l’ensemble des entiers naturels.

Cette ligne se lit donc « pour tout nn entier naturel, PnP_n implique Pn+1P_{n+1} ».

Toutefois, ce résultat nous dit uniquement que si PnP_n est vraie, alors Pn+1P_{n+1} l’est (on dit que PnP_n est une condition suffisante à Pn+1P_{n+1}, tout comme il me suffit d’être capable de porter 10kg pour pouvoir porter 5kg). Pour en profiter, il nous faut un PnP_n de vrai. De la même manière que pour faire tomber une file de dominos, il faut bien commencer par pousser le premier.

Lequel en particulier allons-nous démontrer ? Comme notre objectif est de prouver PnP_n pour tout entier nn supérieur ou égal à 0, il serait appréciable de pouvoir commencer à parcourir la chaîne d’implications à 0 (notez que cette expression de chaîne d’implications n’est pas définie en Mathématiques et sert juste à imager). Cela demande de prouver P0P_0, ce que nous avons fait plus haut. Ainsi nous obtenons :

{P0nN,PnPn+1.\left\{\begin{aligned} &P_0 \\ &\forall n \in \mathbb N, P_n \Rightarrow P_{n+1} \end{aligned}\right..

Il nous suffit alors de partir de P0P_0 et de suivre la chaîne d’implications à l’infini pour montrer que PnP_n est vraie pour tout nn.

  1. P0P_0 est vraie.
  2. Puisque P0P_0 est vraie, P1P_1 l’est car P0P1P_0 \Rightarrow P_1.
  3. Puisque P1P_1 est vraie, P2P_2 l’est car P1P2P_1 \Rightarrow P_2.
  4. Puisque P2P_2 est vraie, P3P_3 l’est car P2P3P_2 \Rightarrow P_3.

Remarquons que si nous avions démontré P1P_1 au lieu de P0P_0, nous aurions obtenu

{P1P0P1P2P3\left\{\begin{aligned} &P_1 \\ &P_0 \Rightarrow P_1 \Rightarrow P_2 \Rightarrow P_3 \Rightarrow \ldots \end{aligned}\right.

et n’aurions pas été capables de déduire de la chaîne d’implications que P0P_0 était vraie.

Le lecteur attentif pourra remarquer toutefois que nous n’avons pas seulement PnPn+1P_n \Rightarrow P_{n+1} mais également la réciproque Pn+1PnP_{n+1} \Rightarrow P_{n} (vous pouvez le démontrer à titre d’exercice). Dans ce cas très précis, nous aurions pu déduire P0P_0 (en remontant la chaîne d’implications en quelque sorte).


Nous avons donc intuitivement démontré PP, c’est-à-dire :

nN,k=0nk=n(n+1)2.\forall n \in \mathbb N, \sum_{k=0}^n k = \frac{n(n+1)}{2}.

Intuitivement, parce que « suivre la chaîne d’implications à l’infini » n’est pas défini mathématiquement et reste donc ambigu. En fait, nous avons utilisé sans le nommer un raisonnement par récurrence et il existe un résultat mathématique nous permettant de conclure.

Dans la section suivante, nous formalisons ce concept et en donnons l’expression générale afin que vous puissiez l’appliquer, dans la suite du tutoriel, à de multiples problèmes. Ce sera aussi l’occasion de redémontrer ce prédicat de façon moins verbeuse.


  1. Notez qu’il est tout à fait possible de définir un prédicat sur un autre ensemble que celui des entiers naturels.

Le raisonnement par récurrence

Dans cette section, nous revenons sur les notions clés illustrées précédemment et introduisons le vocabulaire rattaché au raisonnement par récurrence.

Cette section est principalement une reformulation du raisonnement suivi précédemment donc ne vous inquiétez pas si le contenu vous paraît familier. Pour bénéficier au mieux de l’effet de répétition, nous recommandons de lire cette section un jour ou deux après la précédente.

Nous sommes partis d’un prédicat PP (un énoncé logique dépendant d’une variable) défini sur les entiers naturels, obtenant ainsi une suite de propositions, c’est-à-dire un ensemble de propositions numérotées. Notre objectif est de démontrer le prédicat, c’est-à-dire que tous les éléments de cette suite sont vrais.

Comme il existe une infinité de PnP_n, on ne peut définitivement pas vérifier chacun individuellement. Le moment clé est alors de remarquer que Pn+1P_{n+1} semble découler de PnP_n puis de le prouver. Pour ce faire, nous fixons un nn quelconque et montrons l’implication. On obtient alors intuitivement une chaîne d’implications (intuitivement, car cette expression n’est pas définie mathématiquement) :

{P0P1P1P2P2P3\left\{\begin{aligned} &P_0 \Rightarrow P_1 \\ &P_1 \Rightarrow P_2 \\ &P_2 \Rightarrow P_3 \\ & \ldots \end{aligned}\right.

P0P1P_0 \Rightarrow P_1 signifie littéralement « si P0P_0 est vraie, alors P1P_1 est vraie ». La grande accolade veut dire « et » : P0P_0 implique P1P_1 et P1P_1 implique P2P_2 et… Comme la notation \ldots n’est pas définie en Mathématiques, on écrit plus rigoureusement :

nN,PnPn+1.\forall n \in \mathbb N, P_n \Rightarrow P_{n+1}.

Ce qui se lit « pour tout nn entier naturel, PnP_n implique Pn+1P_{n+1} ». En démontrant que le premier élément (P0P_0) de cette chaîne est vrai, on peut la parcourir jusqu’à l’infini.

  1. P0P_0 est vraie.
  2. Puisque P0P_0 est vraie, P1P_1 l’est car P0P1P_0 \Rightarrow P_1.
  3. Puisque P1P_1 est vraie, P2P_2 l’est car P1P2P_1 \Rightarrow P_2.
  4. Puisque P2P_2 est vraie, P3P_3 l’est car P2P3P_2 \Rightarrow P_3.

On en déduit intuitivement que PnP_n est vraie pour tout nn. Seulement, l’intuition peut être trompeuse et on aime bien en Mathématiques s’appuyer sur des résultats démontrés, même quand ils paraissent évidents. Ça tombe bien, il en existe un (que prouvons en fin de tutoriel) : le principe de récurrence. Il s’exprime très simplement :

{P0nN,PnPn+1nN,Pn.\left\{\begin{aligned} &P_0 \\ &\forall n \in \mathbb N, P_n \Rightarrow P_{n+1} \end{aligned}\right. \Rightarrow \forall n \in \mathbb N, P_n.

Et il se lit : « si P0P_0 est vraie et que pour tout nn entier naturel, PnP_n implique Pn+1P_{n+1}, alors PnP_n est vraie pour tout entier naturel nn ».

Démontrer un résultat (en suivant un raisonnement) par récurrence consiste donc en deux étapes indépendantes :

  • Initialisation : prouver P0P_0 ;
  • Hérédité : prouver nN,PnPn+1\forall n \in \mathbb N, P_n \Rightarrow P_{n+1}.

Quand l’initialisation et l’hérédité sont faites, on peut appliquer le principe de récurrence pour déduire que le prédicat est vrai :

nN,Pn.\forall n \in \mathbb N, P_n.

Retour sur la somme des entiers de 0 à nn

Maintenant que nous avons formalisé les concepts derrière le raisonnement par récurrence, regardons comment nous pourrions rédiger la démonstration de la section précédente rigoureusement (et, il faut l’avouer, de façon un peu lourde ; en pratique la rédaction peut être plus concise, du moment que l’initialisation et l’hérédité apparaissent clairement et sont suffisamment justifiées).

Définition du prédicat

Considérons le prédicat PP défini par :

nN\forall n \in \mathbb N, PnP_n : « k=0nk=n(n+1)2\sum_{k=0}^n k = \frac{n(n+1)}{2} ».

Nous démontrons PP par récurrence.1

Initialisation

On a facilement :

k=00k=0=0(0+1)2.\sum_{k=0}^0 k = 0 = \frac{0(0+1)}{2}.

Donc P0P_0 est vraie.

Hérédité

Fixons un entier naturel nn quelconque et supposons que PnP_n est vraie, c’est-à-dire que cette égalité est vérifiée :

k=0nk=n(n+1)2.\sum_{k=0}^n k = \frac{n(n+1)}{2}.

Montrons alors Pn+1P_{n+1}, soit :

k=0n+1k=(n+1)(n+2)2.\sum_{k=0}^{n+1} k = \frac{(n+1)(n+2)}{2}.

On a :

Pnk=0nk=n(n+1)2(n+1)+k=0nk=(n+1)+n(n+1)2k=0n+1k=(n+1)+n(n+1)2k=0n+1k=2(n+1)+n(n+1)2k=0n+1k=(n+1)(n+2)2Pn+1.\begin{aligned} P_n &\Rightarrow \sum_{k=0}^n k = \frac{n(n+1)}{2} \\ &\Rightarrow (n+1) + \sum_{k=0}^n k = (n+1) + \frac{n(n+1)}{2} \\ &\Rightarrow \sum_{k=0}^{n+1} k = (n+1) + \frac{n(n+1)}{2} \\ &\Rightarrow \sum_{k=0}^{n+1} k = \frac{2(n+1) + n(n+1)}{2} \\ &\Rightarrow \sum_{k=0}^{n+1} k = \frac{(n+1)(n+2)}{2} \\ &\Rightarrow P_{n+1}. \end{aligned}

En résumé :

PnPn+1.P_n \Rightarrow P_{n+1}.

Comme nous avons effectué la démonstration avec un nn quelconque, on déduit :

nN,PnPn+1.\forall n \in \mathbb N, P_n \Rightarrow P_{n+1}.

Conclusion

Nous avons démontré :

{P0nN,PnPn+1.\left\{\begin{aligned} &P_0 \\ &\forall n \in \mathbb N, P_n \Rightarrow P_{n+1} \end{aligned}\right..

Par principe de récurrence, PnP_n est vraie pour tout entier naturel nn, c’est-à-dire :

nN,k=0nk=n(n+1)2.\forall n \in \mathbb N, \sum_{k=0}^n k = \frac{n(n+1)}{2}.

En résumé, le principe de récurrence nous a permis de démontrer un prédicat défini sur l’ensemble des entiers naturels. Mais peut-on l’appliquer à des prédicats définis sur d’autres ensembles ?

Dans la section suivante, nous résumons de façon un peu plus abstraite notre démarche pour en extraire le sens fondamental.


  1. Parce que nous remarquons que Pn+1P_{n+1} découle de PnP_n. Prendre cette décision n’est pas toujours aussi évident, mais rassurez-vous : vous détecterez de plus en plus facilement ce genre de cas avec l’expérience.

Plus généralement : des suites de propositions

Jusqu’à présent, nous avons travaillé avec un prédicat défini sur N\mathbb N, c’est-à-dire que la valeur que prenait la variable dans l’énoncé logique était égale au rang de la proposition : pour obtenir P0P_0 nous avons remplacé nn par 0, pour obtenir P1P_1 nous avons substitué nn par 1, etc. Puis, une fois l’initialisation et l’hérédité prouvées, le fait que toutes les propositions étaient vraies a paru intuitif.

  1. P0P_0 est vraie.
  2. Puisque P0P_0 est vraie, P1P_1 l’est car P0P1P_0 \Rightarrow P_1.
  3. Puisque P1P_1 est vraie, P2P_2 l’est car P1P2P_1 \Rightarrow P_2.

Mais le principe de récurrence peut s’appliquer à toute suite de propositions. En effet, on peut reformuler ses deux étapes ainsi :

  • Initialisation : la première proposition de la suite est vraie ;
  • Hérédité : toute proposition de la suite implique sa successeur.

Quand on a l’initialisation et l’hérédité, le principe de récurrence nous dit que toute proposition de la suite est vraie, ce qui est aussi intuitif que précédemment.

  1. La première proposition est vraie (initialisation).
  2. Puisque la première proposition est vraie, la deuxième (sa successeur) l’est (par hérédité).
  3. Puisque la deuxième proposition est vraie, la troisième l’est.

Autrement dit, le raisonnement par récurrence peut s’envisager pour démontrer des prédicats formant des suites de propositions, c’est-à-dire des prédicats dont les éléments peuvent être numérotés. Ce n’est pas le cas de tout prédicat. Par exemple, l’ensemble R\mathbb R des nombres réels est ordonné (0.33<0.660.33 < 0.66) mais n’est pas discret : quelle proposition suivrait P0P_0 ? Serait-ce P0.1P_{0.1} ? Ou bien P0.01P_{0.01} ? P0.0000000001P_{0.0000000001} ? Ça ne se termine jamais : nous ne pouvons pas définir le successeur de P0P_0.

Pour illustrer le fait que le principe de récurrence s’applique à n’importe quel ensemble de propositions numérotées, considérons le prédicat suivant :

PP : « pour tout entier nn pair positif ou nul, (1)n=1(-1)^n = 1 ».

Les premiers éléments de cette suite de propositions sont :

  • P0P_0 : « (1)0=1(-1)^0 = 1 » ;
  • P1P_1 : « (1)2=1(-1)^2 = 1 » ;
  • P2P_2 : « (1)4=1(-1)^4 = 1 ».

On remarque que la valeur que prend la variable dans l’énoncé logique n’est pas la même que le rang de la proposition, mais ça ne nous empêche pas de démontrer ce prédicat par récurrence :

Initialisation

Par convention, (1)0=1(-1)^0 = 1, donc P0P_0 est vraie.

Hérédité

Fixons un entier positif ou nul kk et montrons que PkP_k (« (1)2k=1(-1)^{2k} = 1 ») implique Pk+1P_{k+1} (« (1)2(k+1)=1(-1)^{2(k+1)} = 1 ») :

(1)2k=1(1)2k×(1)=1(1)2k×(1)×(1)=1(1)2k+2=1(1)2(k+1)=1.\begin{aligned} (-1)^{2k} = 1 &\Rightarrow (-1)^{2k} \times (-1) = -1 \\ &\Rightarrow (-1)^{2k} \times (-1) \times (-1) = 1 \\ &\Rightarrow (-1)^{2k+2} = 1 \\ &\Rightarrow (-1)^{2(k+1)} = 1. \end{aligned}

Donc PkPk+1P_k \Rightarrow P_{k+1}. Comme P0P_0 est vraie, on déduit par principe de récurrence :

Pour tout entier nn pair positif ou nul, (1)n=1(-1)^n = 1. 

La valeur nn que prend la variable dans l’énoncé logique est égale à 2k2k, où kk est le rang de la proposition (k=0k = 0 désignant la première).


En résumé, le principe de récurrence nous permet de démontrer une suite de propositions PnP_n telle que :

  • La première est vraie ;
  • Toute proposition implique sa successeur dans la suite.

À ce niveau du tutoriel, vous avez idéalement assimilé le principe de récurrence et les concepts sous-jacents : prédicat, implication, initialisation et hérédité. Si ce n’est pas tout à fait le cas, pas de panique : dans la prochaine partie, nous fournissons des exercices pour vous permettre de manipuler ces notions et vous aider à vous familiariser avec.