Le principe de récurrence - Le raisonnement par récurrence • Bibliothèque • Zeste de Savoir

Dans cette partie, nous introduisons le principe de récurrence, d’abord au travers de l’exemple de la somme des entiers de 0 à $n$ 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
Le raisonnement par récurrence
Plus généralement : des suites de propositions

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 $n$  :

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 $n$ . Avant d’avancer, remarquons que cette écriture n’est pas très claire. En effet, pour $n = 5$ , on conclut facilement que la partie de gauche est égale à $1 + 2 + 3 + 4 + 5$ . Mais qu’en est-il pour $n = 2$  ? On se doute qu’il faut se débarrasser du 3 pour obtenir $1 + 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 $n$  :

\sum_{k=0}^n k.

Ce qui signifie littéralement « la somme des entiers $k$ compris entre 0 inclus et $n$ 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 :

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

En Mathématiques, on dit que $P_n$ est une proposition, c’est-à-dire un énoncé (ici une égalité) pouvant être soit vrai soit faux. L’ensemble des $P_n$ forme ce qu’on appelle un prédicat (noté $P$ ), c’est-à-dire un énoncé logique paramétré par une variable (ici $n$ ). Comme cette dernière peut valoir n’importe quel entier naturel, on dit que $P$ est défini sur l’ensemble des entiers naturels.¹ 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 :

(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 :

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

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

$P_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 $P_n$ désigne notre énoncé logique (notre égalité) pour $n$ un entier naturel fixé. Dans la suite, nous nous attaquons à une question récurrente (ahah) en Mathématiques :

Peut-on démontrer $P$  ? Autrement dit, peut-on démontrer que la proposition $P_n$ est vraie, quel que soit $n$ (entier naturel) ?

Démontrons notre prédicat

Comme il existe une infinité d’entiers naturels, on ne peut définitivement pas vérifier chaque $P_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 $P_0$ , $P_1$ et $P_2$  ; on remarquera d’ailleurs qu’elles sont vraies).

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

\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 $P_{n+1}$ , on obtient ceux de $P_n$ et peut alors démontrer que si $P_n$ est vraie, alors $P_{n+1}$ est vraie. On note cela $P_n \Rightarrow P_{n+1}$ et prononce «  $P_n$ implique $P_{n+1}$  ». L’implication se prouve de cette manière :

\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 $P_n \Rightarrow P_{n+1}$ . Mais vous remarquerez que nous avons jusqu’ici considéré un $n$ quelconque : nous n’avons supposé rien d’autre que sa nature d’entier naturel. Autrement dit, cette implication est valable pour tout entier naturel $n$  !

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

P_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 :

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

Où :

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

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

Toutefois, ce résultat nous dit uniquement que si $P_n$ est vraie, alors $P_{n+1}$ l’est (on dit que $P_n$ est une condition suffisante à $P_{n+1}$ , tout comme il me suffit d’être capable de porter 10kg pour pouvoir porter 5kg). Pour en profiter, il nous faut un $P_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 $P_n$ pour tout entier $n$ 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 $P_0$ , ce que nous avons fait plus haut. Ainsi nous obtenons :

\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 $P_0$ et de suivre la chaîne d’implications à l’infini pour montrer que $P_n$ est vraie pour tout $n$ .

$P_0$ est vraie.
Puisque $P_0$ est vraie, $P_1$ l’est car $P_0 \Rightarrow P_1$ .
Puisque $P_1$ est vraie, $P_2$ l’est car $P_1 \Rightarrow P_2$ .
Puisque $P_2$ est vraie, $P_3$ l’est car $P_2 \Rightarrow P_3$ .
…

Remarquons que si nous avions démontré $P_1$ au lieu de $P_0$ , nous aurions obtenu

\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 $P_0$ était vraie.

Le lecteur attentif pourra remarquer toutefois que nous n’avons pas seulement $P_n \Rightarrow P_{n+1}$ mais également la réciproque $P_{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 $P_0$ (en remontant la chaîne d’implications en quelque sorte).

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

\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.

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 $P$ (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 $P_n$ , on ne peut définitivement pas vérifier chacun individuellement. Le moment clé est alors de remarquer que $P_{n+1}$ semble découler de $P_n$ puis de le prouver. Pour ce faire, nous fixons un $n$ 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) :

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

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

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

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

$P_0$ est vraie.
Puisque $P_0$ est vraie, $P_1$ l’est car $P_0 \Rightarrow P_1$ .
Puisque $P_1$ est vraie, $P_2$ l’est car $P_1 \Rightarrow P_2$ .
Puisque $P_2$ est vraie, $P_3$ l’est car $P_2 \Rightarrow P_3$ .
…

On en déduit intuitivement que $P_n$ est vraie pour tout $n$ . 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 :

\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 $P_0$ est vraie et que pour tout $n$ entier naturel, $P_n$ implique $P_{n+1}$ , alors $P_n$ est vraie pour tout entier naturel $n$  ».

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

Initialisation : prouver $P_0$  ;
Hérédité : prouver $\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 :

\forall n \in \mathbb N, P_n.

Retour sur la somme des entiers de 0 à $n$

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 $P$ défini par :

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

Nous démontrons $P$ par récurrence.¹

Initialisation

On a facilement :

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

Donc $P_0$ est vraie.

Hérédité

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

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

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

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

On a :

\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é :

P_n \Rightarrow P_{n+1}.

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

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

Conclusion

Nous avons démontré :

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

Par principe de récurrence, $P_n$ est vraie pour tout entier naturel $n$ , c’est-à-dire :

\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.

Parce que nous remarquons que $P_{n+1}$ découle de $P_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 $\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 $P_0$ nous avons remplacé $n$ par 0, pour obtenir $P_1$ nous avons substitué $n$ 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.

$P_0$ est vraie.
Puisque $P_0$ est vraie, $P_1$ l’est car $P_0 \Rightarrow P_1$ .
Puisque $P_1$ est vraie, $P_2$ l’est car $P_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.

La première proposition est vraie (initialisation).
Puisque la première proposition est vraie, la deuxième (sa successeur) l’est (par hérédité).
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 $\mathbb R$ des nombres réels est ordonné ( $0.33 < 0.66$ ) mais n’est pas discret : quelle proposition suivrait $P_0$  ? Serait-ce $P_{0.1}$  ? Ou bien $P_{0.01}$  ? $P_{0.0000000001}$  ? Ça ne se termine jamais : nous ne pouvons pas définir le successeur de $P_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 :

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

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

$P_0$  : «  $(-1)^0 = 1$  » ;
$P_1$  : «  $(-1)^2 = 1$  » ;
$P_2$  : «  $(-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$ , donc $P_0$ est vraie.

Hérédité

Fixons un entier positif ou nul $k$ et montrons que $P_k$ («  $(-1)^{2k} = 1$  ») implique $P_{k+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 $P_k \Rightarrow P_{k+1}$ . Comme $P_0$ est vraie, on déduit par principe de récurrence :

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

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

En résumé, le principe de récurrence nous permet de démontrer une suite de propositions $P_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.