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

article-MathOS

 

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

Un autre texte, proposant une étude plus approfondie du raisonnement par récurrence et des exemples plus consistants est consultable ici.

 

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

Un nombre entier non pair est dit impair; on peut le mettre 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 :

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.

Posons-nous maintenant la question suivante :

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 3, 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, pour tout n\geqslant1, 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.

Si l’on effectue la construction décrite plus haut pour les valeurs de n comprises entre 2 et 5, on trouve :

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

Tout ceci 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 n ne permet pas conclure dans le cas général !

Au fait, sauriez-vous trouver une formule générale pour R_{n}, en justifiant rigoureusement votre calcul ? N’hésitez pas à m’écrire (en utilisant le formulaire de contact) et je serai ravi de publier votre réponse.

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. Le lecteur intéressé pourra lire à ce sujet la section 5 de l’article Qu’est-ce qu’une conjecture ? mais revenons à nos moutons…

La question centrale est :

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 ?

Voici une réponse à cette question. Elle constitue le raisonnement par récurrence :

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

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 :

    \[ S_{n+1}=1+2+\cdots+n+\left(n+1\right)=S_{n}+n+1=\frac{n\left(n+1\right)}{2}+n+1 \]

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 :

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.

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 conjecture donc naturellement que :

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

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

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

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

Là encore, 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

 

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) \]

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 :

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

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 {\displaystyle \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 première 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 ici 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. N’hésitez pas à commenter cet article : toutes vos questions, remarques ou suggestions d’amélioration seront les bienvenues.

Partager cet article
  • 1
  •  
  •  
  •  
  •  

Laisser un commentaire

Fermer le menu