Qu'est-ce qu'une preuve par récurrence ?

Cet article se veut très élémentaire : il est donc très incomplet.

On trouvera dans cet autre texte une étude plus approfondie du raisonnement par récurrence, ainsi que des exemples plus consistants.

1 – Une question de parité

Tout le monde sait ce qu’est un nombre pair : il s’agit tout simplement du double d’un nombre entier.

Par exemple, 1450 est pair puisque 1450 = 2 $\times$ 725.

Un nombre entier non pair est dit impair. On peut l’écrire sous la forme $2k+1$ , où $k$ est entier. Détaillons cette dernière affirmation :

Si $n$ est un entier impair, notons $2k$ le plus grand entier pair inférieur à $n.$

On constate que $2k<n<2k+2.$ Il en résulte que $n=2k+1.$

Il est facile de voir que la somme de deux entiers pairs $p$ et $q$ est encore un entier pair. En effet, en notant $p=2a$ et $q=2b,$ il vient $p+q=2a+2b=2\left(a+b\right).$ Et comme $a+b$ est entier (c’est la somme de deux entiers), alors $p+q$ est pair.

Enonçons une règle plus générale :

Parité de la somme de deux entiers

Etant donnés deux entiers $p$ et $q,$ deux cas se présentent :

Si $p$ et $q$ sont de même parité (tous deux pairs, ou bien tous
deux impairs), alors $p+q$ est pair.
Si $p$ et $q$ sont de parités contraires, alors $p+q$ est impair.

Le lecteur est invité à établir ce résultat, en exercice.

A présent, posons-nous la question suivante :

Question :

Etant donné un entier naturel $n,$ quelle est la parité de $n^{2}+5n+1$ ?

Notons $A_{n}=n^{2}+5n+1$ et regardons ce qui se passe pour les petites valeurs de $n.$

De simples calculs révèlent que :

$A_{0}=1,\qquad A_{1}=7,\qquad A_{2}=15,\qquad A_{3}=25,\qquad A_{4}=37$

$A_{5}=51,\qquad A_{6}=67,\qquad A_{7}=85,\qquad A_{8}=105,\qquad A_{9}=127$

On conjecture aussitôt que $A_{n}$ est impair, quel que soit $n,$ ce qui est facile à établir directement ! On peut en effet écrire, pour tout $n\in\mathbb{N}$ :

$A_{n}=n\left(n+1\right)+4n+1$

Or, d’une part, l’entier $n\left(n+1\right)$ est pair, car c’est le produit de deux entiers consécutifs (l’un des deux entiers $n$ ou $n+1$ étant pair, leur produit aussi).

Et d’autre part, l’entier $4n+1$ est évidemment impair.

Ainsi $A_{n}$ est impair, puisque c’est la somme de deux entiers de parités contraires.

Notre conjecture est devenue un théorème. Un théorème bien modeste, certes, mais que nous reprendrons à la section 4, en guise d’exemple de preuve par récurrence.

2 – Fausses Impressions

L’examen des quelques premières valeurs de $n$ pouvait-il suffire à nous convaincre de la validité de notre précédente conjecture ? La réponse est non, comme le prouvent les deux exemples suivants.

Exemple 1

Pour tout entier $n\geqslant1,$ notons $B_{n}$ l’entier naturel dont l’écriture décimale comporte $n$ chiffres ‘3’ suivis d’un ‘1’. Ainsi :

$B_{1}=31,\qquad B_{2}=331,\qquad B_{3}=3331,\qquad B_{4}=33331,\qquad\text{etc ...}$

Posons-nous la question :

$B_{n}$ est-il toujours un nombre premier ?

On constate que $B_{1},$ $B_{2},$ $B_{3},$ $B_{4},$ $B_{5},$ $B_{6}$ et $B_{7}$ sont tous premiers. Les quelques premières valeurs de $n$ nous mettent donc sur la piste d’un « oui » !

Mais l’histoire s’arrête là puisque :

$B_{8}=333\thinspace333\thinspace331=17\times19\thinspace607\thinspace843$

ce qui prouve que $B_{8}$ est un nombre composé. Un autre scénario de ce type, où l’illusion persiste plus longtemps, apparaît au début de l’article Qu’est-ce qu’une conjecture ?
Et pour en savoir davantage sur les nombres premiers, on pourra consulter l’article Mysterieux nombres premiers.

Exemple 2

Etant donné un entier $n\geqslant2,$ plaçons $n$ points distincts sur un cercle et relions chacun d’eux à tous les autres. Ceci fait apparaître plusieurs régions à l’intérieur du disque : on notera $R_{n}$ leur nombre. La question naturelle est : existe-t-il une formule simple pour $R_{n}$ ?

Notons, avant d’aller plus loin qu’il n’est du tout clair, a priori, que le nombre de régions dépende seulement de $n$ : cet entier pourrait très bien dépendre de la configuration choisie… mais passons.

Effectuons la construction décrite plus haut pour les valeurs de n comprises entre 2 et 5 :

On trouve donc :

$R_{2}=2,\qquad R_{3}=4,\qquad R_{4}=8,\qquad R_{5}=16$

ce qui nous amène naturellement à conjecturer que $R_{n}=2^{n-1},$ pour tout $n\geqslant2.$

Sauf que cette conjecture est fausse ! En effet, $R_{6}=31$ (et non pas $32)$ :

Ces deux exemples montrent qu’il ne faut pas se précipiter ! En d’autres termes :

L’examen d’un nombre fini de valeurs particulières de l’entier n ne permet pas conclure dans le cas général !

Au fait …

Le deuxième exemple est célèbre : c’est le fameux Moser’s Circle Problem, popularisé par le mathématicien austro-canadien Léo Moser (1921 – 1970).
Je vous recommande cette excellente vidéo explicative, sur la chaine 3Blue1Brown !

3 – Preuve par récurrence : Comment ça marche ?

On s’intéresse à un énoncé qui fait intervenir un entier naturel $n,$ et dont la « valeur de vérité » dépend de $n.$ Autrement dit, cet énoncé peut être vrai pour certaines valeurs de $n,$ et faux pour d’autres.

Par exemple, il pourrait s’agir de :

$A_{n}$ : « la somme des $n$ premiers nombres impairs est un carré parfait »,
$B_{n}$ : « le produit de $n$ entiers consécutifs est multiple de $1\times2\times\cdots\times n$ « ,
$C_{n}$ : « $5^{n}+9618$ un nombre premier ».

Il se trouve que $A_{n}$ est vrai pour tout $n$ (voir section 6 du présent article) et qu’il en va de même pour $B_{n}$ (voir l’article Le produit de k entiers consécutifs est multiple de k!).

En revanche, $C_{n}$ est vrai pour certaines valeurs de $n$ (par exemple tous les entiers de 0 à 10, mais pas seulement : les entiers 13, 17, 18, 19 et 24 conviennent aussi) mais pas pour d’autres.

Et comme les mathématiques ne sont pas une science facile (ça se saurait…), ne perdons pas de vue qu’il existe des énoncés qui sont vrais pour toutes les valeurs particulières de $n$ qu’on a pu tester, mais dont personne n’est à ce jour capable de démontrer la validité pour tout $n.$ Par exemple :

$G_{n}$ : Pour tout $n\geqslant2,$ le nombre pair $2n$ est la somme de deux nombres premiers.

Il s’agit de la célèbre conjecture de Goldbach. A ce sujet, le lecteur intéressé pourra consulter l’article Qu’est-ce qu’une conjecture ? mais revenons à nos moutons…

La question centrale est :

Question :

Etant donnés : • un énoncé $E_{n}$ portant sur un entier naturel $n$ , • un entier naturel $N$ ,

Comment peut-on prouver que $E_{n}$ est vrai pour tout $n\geqslant N$ ?

Le raisonnement par récurrence apporte une réponse. Voici en quoi il consiste :

Réponse

➡ On prouve d’une part que $E_{N}$ est vrai.
➡ On prouve d’autre part que, si $E_{n}$ est vrai pour un certain $n\geqslant N,$ alors $E_{n+1}$ est aussi vrai.

Le premier point constitue l’initialisation. Le second indique que l’énoncé est héréditaire (c’est-à-dire que sa validité se transmet de chaque entier $n\geqslant N$ à son successeur).

Intuitivement, comme $E_{N}$ est vrai alors $E_{N+1}$ aussi d’après l’hérédité. Puis, comme $E_{N+1}$ est vrai, alors $E_{N+2}$ aussi toujours d’après l’hérédité. De même, puisque $E_{N+2}$ est vrai, alors $E_{N+3}$ aussi … et ainsi de suite …

En quelque sorte, l’initialisation constitue un « germe » et l’hérédité permet à ce germe de « s’auto développer » à l’infini.

Il est temps pour nous d’aborder quelques exemples fondamentaux de démonstrations par récurrence.

4 – Notre tout premier exemple

Revenons à la question examinée à la section 1. Il s’agissait de prouver que $n^{2}+5n+1$ est impair, quel que soit l’entier naturel $n.$

Pour $n=0,$ c’est vrai ! Ceci règle l’initialisation.

Et si $n^{2}+5n+1$ est impair pour un certain $n,$ alors :

$\left(n+1\right)^{2}+5\left(n+1\right)+1=\left(n^{2}+5n+1\right)+\left(2n+6\right)$

apparaît comme la somme de deux entiers de parités contraires; c’est donc un entier impair. Et voilà pour l’hérédité.

Nous disposons donc de deux démonstrations d’un même résultat : directement (cf. section 1) et par récurrence. Passons à un autre exemple.

5 – Un grand classique !

Dans ce qui suit, la somme des entiers de 1 jusqu’à $n$ sera notée $S_{n}.$ Autrement dit :

$S_{n}=1+2+\cdots+n$

ou bien, avec une notation plus « professionnelle » :

$S_{n}=\sum_{k=1}^{n}k$

Si vous n’êtes pas habitué à l’usage de cette notation $\Sigma$ (sigma), pas de panique ! Je ne vais pas m’en servir ici, mais vous pourrez éventuellement commencer à l’étudier en lisant l’article Manipulation du symbole $\Sigma$

Pour commencer, calculons $S_{n}$ pour de petites valeurs de $n$ :

$S_{1}=1\qquad S_{2}=1+2=3\qquad S_{3}=1+2+3=6$

et ainsi de suite. Il est facile de construire une table donnant les valeurs de $S_{n}$ pour $1\leqslant n\leqslant10$ :

Avec un peu d’attention, on observe que, par exemple :

$S_{4}=10=\frac{4\times5}{2}\qquad S_{5}=15=\frac{5\times6}{2}\qquad S_{6}=21=\frac{6\times7}{2}$

Evidemment, ces observations ne prouvent rien de général à elles-seules. Toutefois, elles conduisent certainement à conjecturer que :

Conjecture

Pour tout $n\geqslant1,$ la somme des $n$ premiers entiers est $S_{n}={\displaystyle \frac{n\left(n+1\right)}{2}}$

Nous allons maintenant démontrer ceci, par récurrence.

Pour l’initialisation, il s’agit de vérifier que $S_{1}=\frac{1\left(1+1\right)}{2},$ et c’est bien le cas.

Pour l’hérédité, on suppose que $S_{n}=\frac{n\left(n+1\right)}{2}$ pour un certain $n\geqslant1$ et l’on prouve que, sous cette hypothèse : $S_{n+1}=\frac{\left(n+1\right)\left(n+2\right)}{2}.$

Voici comment :

$\begin{eqnarray*}S_{n+1} & = & 1+2+\cdots+n+\left(n+1\right)\\& = & S_{n}+n+1\\& = & \frac{n\left(n+1\right)}{2}+n+1\end{eqnarray*}$

donc :

$S_{n+1}=\left(n+1\right)\left(\frac{n}{2}+1\right)$

soit finalement :

$S_{n+1}=\frac{\left(n+1\right)\left(n+2\right)}{2}$

comme souhaité.

Signalons que ce résultat est parfaitement accessible sans récurrence. On raconte que le grand mathématicien allemand Carl Friedrich Gauss découvrit, lorsqu’il était encore enfant, la preuve suivante. Le double de la somme demandée se ré-écrit en associant les termes $1$ et $n,$ les termes $2$ et $n-1,$ etc … ce qui fait apparaître $n$ groupes de deux termes, chaque groupe formant un total de $n+1.$ En symboles :

$\begin{eqnarray*}2\thinspace S_{n} & = & \left(1+2+\cdots+\left(n-1\right)+n\right)+\left(n+\left(n-1\right)+\cdots+2+1\right)\\& = & \left(1+n\right)+\left(2+\left(n-1\right)\right)+\cdots+\left(\left(n-1\right)+2\right)+\left(n+1\right)\\& = & n\left(n+1\right)\end{eqnarray*}$

et donc :

$S_{n}=\frac{n\left(n+1\right)}{2}$

6 – La somme des n premiers nombres impairs

Le premier nombre impair (positif) est 1. Les trois suivants sont 3, 5 et 7. Quel est le $n-$ ème ?

Il n’est pas difficile de deviner la formule générale :

Conjecture 1

Pour tout $n\geqslant1,$ le $n-$ ème nombre impair est $2n-1.$

A ce stade, deux situations sont envisageables : si cette affirmation vous paraît évidente, nous allons pouvoir passer directement à la suite ! Et sinon, il va falloir l’établir… par récurrence.

Preuve de la conjecture 1 (cliquer pour déplier / replier)

Notons donc $i_{n}$ le $n-$ ème nombre impair. Il est clair que $i_{1}=1=2\times1-1,$ ce qui règle la question de l’initialisation. Ensuite, en supposant que $i_{n}=2n-1$ pour un certain entier $n\geqslant1,$ on observe que :

$i_{n+1}=i_{n}+2=\left(2n-1\right)+2=2n+1=2\left(n+1\right)-1$

et ceci prouve l’hérédité. A présent, aucun doute ne subsiste quant à l’affirmation encadrée ci-dessus.

Passons à la question qui nous occupe dans cette section : que vaut la somme des $n$ premiers nombres impairs ?

En la notant $T_{n},$ on calcule aisément :

$T_{1}=1,\qquad T_{2}=1+3=4,\qquad T_{3}=1+3+5=9,\qquad\text{etc...}$

Tout comme nous l’avions fait pour $S_{n}$ à la section précédente, on peut placer dans une table les nombres $T_{n}$ pour $1\leqslant n\leqslant10$ :

De toute évidence, ce sont les dix premiers carrés parfaits qui apparaissent ici. On est donc naturellement que conduit à la :

Conjecture 2

Pour tout $n\geqslant1,$ la somme des $n$ premiers nombres impairs est $T_{n}=n^{2}.$

Après avoir conjecturé, il faut démontrer. Et vous commencez à connaître la chanson : on va procéder par récurrence.

Preuve de la conjecture 2 (cliquer pour déplier / replier)

Pour l’initialisation, on se borne à observer que :

$T_{1}=1=1^{2}$

Pour l’hérédité, on suppose que $T_{n}=n^{2}$ pour un certain $n\geqslant1;$ on calcule alors :

$T_{n+1}=T_{n}+\left(2n+1\right)=n^{2}+2n+1$

Nos connaissances de collège sur les identités remarquables nous permettent de reconnaître que cette dernière quantité n’est autre que $\left(n+1\right)^{2}.$

C’est exactement ce qu’on voulait obtenir.

Notons que, comme pour le résultat établi à la section 5, une preuve directe est envisageable. Il suffit (en utilisant la notation $S_{n}$ introduite à la section précédente) d’observer que :

$\begin{eqnarray*}T_{n} & = & \left(2\times1-1\right)+\left(2\times2-1\right)+\cdots+\left(2n-1\right)\\& = & 2\left(1+2+\cdots+n\right)-\left(1+1+\cdots+1\right)\\& = & 2S_{n}-n\\& = & n\left(n+1\right)-n\\& = & n^{2}\end{eqnarray*}$

C’est la troisième fois qu’on démontre un résultat par récurrence… pour se rendre compte ensuite qu’on pouvait l’établir directement. Le principal avantage d’une preuve directe est qu’on n’a pas besoin de conjecturer le résultat à démontrer ! Ce résultat apparaît « naturellement », au terme d’un calcul.

Mais le raisonnement par récurrence n’en est pas pour autant inutile ! Dans beaucoup de situations, on ne sait pas vraiment faire autrement. Les deux sections suivantes proposent des exemples de telles situations.

7 – Une identité remarquable

Proposition

Pour tout entier $n\geqslant2$ et tout nombre réel $x,$ on a la formule de factorisation :

$1-x^{n}=\left(1-x\right)\left(1+x+\cdots+x^{n-1}\right)\qquad(\diamondsuit)$

Preuve de la proposition (cliquer pour déplier / replier)

Démontrons ceci par récurrence (le réel $x$ étant fixé). Pour $n=2,$ c’est une égalité bien connue depuis le collège :

$1-x^{2}=\left(1-x\right)\left(1+x\right)$

Supposons l’égalité $\left(\diamondsuit\right)$ vraie pour un certain $n\geqslant2;$ alors :

$\begin{eqnarray*}1-x^{n+1} & = & 1-x+x\left(1-x^{n}\right)\\& = & 1-x+x\left(1-x\right)\left(1+x+\cdots+x^{n-1}\right)\\& = & 1-x+\left(1-x\right)\left(x+x^{2}+\cdots+x^{n}\right)\\& = & \left(1-x\right)\left(1+x+\cdots+x^{n}\right)\end{eqnarray*}$

comme souhaité.

La formule $\left(\diamondsuit\right)$ est fondamentale. Pour $x\neq1,$ elle prend la forme :

$1+x+\cdots+x^{n-1}=\frac{1-x^{n}}{1-x}$

Si l’on considère une suite géométrique $\left(u_{n}\right)_{n\in\mathbb{N}}$ de raison $x,$ alors les $n$ premiers termes de cette suite sont :

$u_{0},\quad u_{1}=xu_{0},\quad u_{2}=x^{2}u_{0},\quad\cdots\quad u_{n-1}=x^{n-1}u_{0}$

et leur somme est donc donnée par :

$\boxed{u_{0}+u_{1}+\cdots+u_{n-1}=u_{0}\frac{1-x^{n}}{1-x}}$

Une autre conséquence directe de la formule $\left(\diamondsuit\right)$ est l’identité remarquable :

$\boxed{a^{n}-b^{n}=\left(a-b\right)\left(a^{n-1}+a^{n-2}b+\cdots+ab^{n-2}+b^{n-1}\right)}$

qui est valable pour tout $n\geqslant2$ et tout couple $\left(a,b\right)$ de nombres réels.

Passons à un exemple à la fois plus anecdotique et plus élaboré.

8 – Une suite ultimement croissante

Fixons un réel $s>0$ et considérons la suite $\left(u_{n}\right)_{n\geqslant0}$ définie par :

$u_{0}=s\qquad\text{et}\qquad\forall n\in\mathbb{N},\thinspace u_{n+1}=\sqrt{n+u_{n}}$

Par exemple, si $s=100,$ voici des valeurs approchées des dix premiers termes de cette suite :

$u_{0}=100\qquad u_{1}=10\qquad u_{2}\simeq3,317\qquad u_{3}\simeq2,306\qquad u_{4}\simeq2,303$

$u_{5}\simeq2,511\qquad u_{6}\simeq2,741\qquad u_{7}\simeq2,956\qquad u_{8}\simeq3,155\qquad u_{9}\simeq3,340$

Les premières valeurs vont en diminuant, mais elles semblent remonter à partir de $u_{4}.$ Des calculs supplémentaires montreraient que cette tendance se poursuit, mais – là encore – on ne montrera rien de général avec des calculs de ce type, aussi nombreux soient-ils.

Nous allons prouver que, peu importe la valeur choisie pour $s,$ la suite $\left(u_{n}\right)_{n\geqslant0}$ est « strictement croissante à partir d’un certain rang », c’est-à-dire :

Proposition A

Il existe $N\in\mathbb{N}$ tel que $u_{n+1}>u_{n}$ pour tout $n\geqslant N\qquad\left(\spadesuit\right)$

Pour cela, commençons par établir un résultat plus faible, à savoir :

Proposition B

Il existe un entier $N\in\mathbb{N}$ tel que $u_{N+1}>u_{N}\qquad\left(\star\right)$

Dans le cas contraire, à savoir que $u_{n+1}\leqslant u_{n}$ pour tout $n\in\mathbb{N},$ la suite serait décroissante donc majorée (par $s)$ ce qui est absurde puisque $u_{n}\geqslant\sqrt{n-1}$ pour tout $n\geqslant1$ (et ceci impose bien sûr que $\lim_{n\rightarrow\infty}u_{n}=+\infty).$

Le résultat $\left(\star\right)$ est acquis. Montrons maintenant $\left(\spadesuit\right)$ en procédant par récurrence.

On sait déjà que $u_{N+1}>u_{N}$ ce qui donne l’initialisation.

Supposons que, pour un certain $n\geqslant N,$ on ait : $u_{n+1}>u_{n}.$ Alors :

$u_{n+2}=\sqrt{n+1+u_{n+1}}>\sqrt{n+u_{n}}=u_{n+1}$

ce qui achève la preuve.

9 – Une remarque « philosophique » pour conclure

Pour s’assurer de la validité d’un énoncé $E_{n}$ quelle que soit la valeur de l’entier naturel $n,$ la première idée qui peut venir à l’esprit est de tester successivement les cas $n=0,$ $n=1,$ $n=2,$ etc…

Deux problèmes majeurs surviennent :

L’examen d’un nombre fini de cas ne peut pas suffire (voir la deuxième section du présent article)
L’examen de tous les cas, un à un, est impossible… puisqu’il en existe une infinité !

La puissance du raisonnement par récurrence apparaît en pleine lumière : on traite une infinité de cas en utilisant seulement un nombre fini de mots !

A méditer …

Je vous remercie d’avoir pris le temps de me lire jusqu’au bout 🙂

Vos questions ou remarques seront toujours les bienvenues. Vous pouvez laisser un commentaire ci-dessous ou bien passer par le formulaire de contact.

Partager cet article

Cet article a 3 commentaires

Oncle Junior 30 Août 2022 Répondre

Ah oui ! Merci pour cette précision 😊
Oncle Junior 30 Août 2022 Répondre

Bonjour,
Merci pour cet article.
C’est une micro remarque, mais avant la partie 7 vous annoncez des résultats difficilement démontrables par voie directe, mais l’exemple de la partie 7 peut se faire en faisant apparaître une somme télescopique dans le membre de droite ?
Bien à vous.
1. René Adad 30 Août 2022 Répondre
  
  Vous avez en partie raison. On peut en effet écrire ceci, pour tout réel (ou complexe) $x$ et tout entier $n\geqslant2$ :
  
  $(1-x)\sum_{k=0}^{n-1}x^k=\sum_{k=0}^{n-1}x^k-\sum_{k=0}^{n-1}x^{k+1}=\sum_{k=0}^{n-1}(x^k-x^{k+1})=1-x^n$
  
  Cela dit, si l’on gratte un peu, comment se démontre la formule des sommes télescopiques ? Par récurrence …