Quelques jolies preuves par récurrence

Dans l’article Qu’est-ce qu’une preuve par récurrence ?, la notion de démonstration par récurrence a été présentée dans son plus simple appareil et assortie de quelques exemples.

Pour l’essentiel, on y a expliqué ceci : étant donnés un entier naturel N et un énoncé E_{n} faisant intervenir un entier n, il suffit pour montrer que E_{n} est vrai pour tout n\geqslant N d’établir deux choses :

E_{N} est vrai

• Pour tout n\geqslant N, si E_{n} est vrai, alors E_{n+1} est aussi vrai.

Ceci a été “expliqué” mais non “démontré”…
Une preuve rigoureuse, lorsque N=0, fait l’objet de la première section. Le cas général s’en déduit facilement.

 

1 – Le principe de récurrence “classique”

On utilisera dans ce qui suit une propriété fondamentale, à savoir que toute partie non vide de \mathbb{N} possède un plus petit élément.

Considérons un énoncé E_{n}, portant sur un entier n\in\mathbb{N} et supposons, d’une part, que E_{0} est vrai (initialisation) et, d’autre part, que si E_{n} est vrai pour un certain n, alors E_{n+1} est aussi vrai (hérédité).

Notons V l’ensemble des entiers naturels n\in\mathbb{N} pour lesquels E_{n} est vrai. On va établir, en raisonnant par l’absurde, que V=\mathbb{N}, ce qui signifiera exactement que E_{n} est vrai pour tout n\in\mathbb{N}.

Supposons donc V\neq\mathbb{N}, ce qui revient à dire que \mathbb{N}-V (le complémentaire de V dans \mathbb{N}) est non vide. On peut alors considérer le plus petit élément de \mathbb{N}-V, qu’on notera p.

L’hypothèse 0\in V montre que p\geqslant1. L’entier naturel p-1 n’appartient pas à \mathbb{N}-V, car il est inférieur au plus petit élément de cet ensemble; il appartient donc à V et, vue l’hypothèse d’hérédité, son successeur \left(p-1\right)+1 appartient aussi à V. Bref : p\in V et p\in\mathbb{N}-V, ce qui est absurde.

On a bien prouvé que V=\mathbb{N}.

Dans l’article Qu’est-ce qu’une preuve par récurrence déjà signalé plus haut, on peut lire quelques exemples simples et classiques de démonstrations par récurrence. En voici un de plus, que je trouve personnellement très élégant.

 

2 – Pavage par des triminos

Recouvrir un damier de 2n\times2n cases à l’aide de dominos (chaque domino recouvrant 2 cases) est une opération banale. Et si l’on retire une case ? Evidemment, cela devient impossible puisqu’il restera alors un nombre impair de cases.

Ok. Et si l’on retire deux cases diagonalement opposées, le pavage redevient-il possible ?

Une astuce classique consiste à imaginer que les cases du damier ont été coloriées (blanches et noires, en alternance). Les deux cases supprimées étant de la même couleur, le nombre de cases blanches restantes est distinct du nombre de cases noires restantes ! Ceci montre l’impossibilité de la construction.

trimino

A présent, changeons complètement la règle du jeu : remplaçons les dominos par des “triminos”, c’est-à-dire des pièces de la forme ci-contre. Un trimino recouvre trois cases, disposées en ‘L’. On peut, en le faisant pivoter, le positionner de quatre manières.

Considérons un damier de format 2^{p}\times2^{p} (avec p\geqslant1), qui comporte donc 4^{p} cases. Est-il possible de le recouvrir intégralement au moyen de triminos ?

Il est clair que non, puisque 4^{p} n’est pas multiple de 3.

 

Bon, d’accord… Et si l’on retire une case (peu importe laquelle) ? Cette fois l’argument arithmétique ne donne rien (au sens où aucune contradiction n’apparaît) car 4^{p}-1 est multiple de 3.

Cette dernière affirmation peut se justifier d’au moins deux façons.

→ Soit en raisonnant par récurrence : 4^{1}-1=3 est un multiple de 3 (initialisation) et si 4^{p}-1=3k avec k entier, alors 4^{p+1}-1=4\left(4^{p}-1\right)+3=3\left(4k+1\right) est multiple de 3.

→ Soit en factorisant à l’aide de l’identité remarquable a^{p}-b^{p}=\left(a-b\right)\left(a^{p-1}+a^{p 2}b+\cdots+ab^{p-2}+b^{p-1}\right), en y remplaçant bien sûr a et b par 4 et 1 respectivement; ce qui donne :

    \[ 4^{p}-1=3\left(4^{p-1}+4^{p-2}+\cdots+4+1\right) \]

Il s’avère que notre damier 2^{p}\times2^{p} privé d’une case peut, quel que soit p\geqslant1 et quelle que soit la case retirée, être recouvert par des triminos, ce que nous allons maintenant démontrer … par récurrence.

Pour commencer, l’initialisation est évidente : pour p=1, la zone est recouvrir a précisément la forme d’un trimino.

Supposons maintenant avoir réglé la question pour une certaine valeur de p et considérons alors un damier de format 2^{p+1}\times2^{p+1}, privé d’un case.

Cette case (C) est contenue dans l’un des quatre sous-damiers de format 2^{p}\times2^{p} : en haut à droite (HD), en haut à gauche (HG), en bas à droite (BD) ou en bas à gauche (BG). Pour fixer les idées (comme on dit), mettons qu’il s’agisse de (BG). Dans l’illustration ci-dessous, la case (C) est représentée en rouge.

En appliquant l’hypothèse de récurrence, on peut recouvrir (BG) privé de (C) :

Ensuite (astuce géniale !), on place un trimino au centre de la figure, de manière à occuper une case
de chacun des trois sous-damiers (HD), (HG) et (BD). Ce trimino est représenté ci-dessous en jaune :

 

Notons (C1), (C2) et (C3) ces trois cases. On peut appliquer l’hypothèse de récurrence :

• à (HD) privé de (C1)
• à (HG) privé de (C2)
• à (BD) privé de (C3)

et le tour est joué !

recurrence-trimino-complet

 

3 – Récurrences mal engagées

On tombe parfois sur des énoncés héréditaires, mais qui sont faux pour toutes les valeurs de n.

Le secret ? Un défaut d’initialisation !

Considérons par exemple l’énoncé A_{n} suivant : “l’entier 10^{n}+1 est multiple de 9“.

Si l’on suppose A_{n} vrai pour un certain n\in\mathbb{N}, alors il existe k\in\mathbb{N} tel que 10^{n}+1=9k, et donc :

    \[ 10^{n+1}+1=10\left(10^{n}+1\right)-9=9\left(10k-1\right) \]

Autrement dit A_{n+1} est vrai dès que A_{n} l’est. Mais il n’existe aucune valeur de n pour laquelle A_{n} est vrai !!

Le vice de forme est parfois mieux caché… Nous allons “démontrer” l’étonnant résultat suivant :

Etant donné un entier n\geqslant2 et n points M_{1},\cdots,M_{n} du plan, ces points sont nécessairement alignés.

Manifestement, cette affirmation est vraie pour n=1 et pour n=2. Supposons-la vraie au rang n, pour un certain n\geqslant2, et considérons n+1 points M_{1},\cdots,M_{n},M_{n+1}. On sait, par hypothèse de récurrence, que M_{1},\cdots,M_{n} sont alignés et même chose pour M_{2},\cdots,M_{n+1}. Mais la droite qui porte les points M_{1},\cdots,M_{n} et celle qui porte M_{2},\cdots,M_{n+1} sont nécessairement confondues, puisqu’elles ont en commun les points M_{2} et M_{n}.

Pourtant, le résultat annoncé ne tient pas debout. Alors … où est l’erreur ? La réponse à cette question n’apparaîtra qu’en fin d’article 🙂

 

4 – Récurrences du second ordre

Principe

Considérons un énoncé E_{n} portant sur un entier naturel n et supposons que :

E_{0} et E_{1} sont vrais,

• Pour tout n\geqslant1, si E_{n-1} et E_{n} sont vrais alors E_{n+1} est aussi vrai.

Dans ces conditions, E_{n} est vrai pour tout n.

On peut aisément déduire ceci du principe de récurrence standard (cf. section 1), en appliquant ce dernier à l’énoncé F_{n} suivant : “E_{n-1} et E_{n} sont vrais”. En effet :

• D’une part F_{1} est vrai d’après l’hypothèse 1.

• D’autre part, si F_{n} est vrai pour un certain n\geqslant1, cela signifie que E_{n-1} et E_{n} sont vrais, donc (seconde hypothèse) E_{n+1} est vrai et donc F_{n+1} aussi.

Ainsi F_{n} est vrai pour tout n\geqslant1, ce qui prouve que E_{n} est vrai pour tout n\geqslant0.

Examinons, dans les deux sections suivantes, quatre exemples d’utilisation.

 

5 – Deux exemples anecdotiques

– Exemple 1 –

La suite de Fibonacci \left(F_{n}\right)_{n\in\mathbb{N}} est définie par les relations :

    \[ F_{0}=0,\qquad F_{1}=1,\qquad\forall n\geqslant1,\thinspace F_{n+1}=F_{n}+F_{n-1} \]

Vérifions que, pour tout n\in\mathbb{N} :

    \[ F_{n}<\left(\frac{5}{3}\right)^{n} \]

Cette inégalité est clairement vérifiée pour n=0 et pour n=1.

Supposons-la vraie aux rangs n-2 et n-1, pour un certain n\geqslant2. Alors :

    \[ F_{n}=F_{n-1}+F_{n-2}<\left(\frac{5}{3}\right)^{n-1}+\left(\frac{5}{3}\right)^{n-2}=\frac{5^{n-2}\times24}{3^{n}}<\frac{5^{n-2}\times25}{3^{n}}=\left(\frac{5}{3}\right)^{n} \]

comme souhaité.

On pourra regarder l’exercice n° 2 de la fiche 01 sur la récurrence pour établir une minoration analogue de F_{n}.

 

– Exemple 2 –

Posons pour tout n\in\mathbb{N} :

    \[ I_{n}=\int_{0}^{1}\frac{t^{n}}{\left(t+1\right)^{2}}\thinspace dt \]

et montrons que :

    \[ \forall n\in\mathbb{N},\thinspace\exists\left(a_{n},b_{n}\right)\in\mathbb{Q}^{2};\thinspace I_{n}=a_{n}+b_{n}\ln\left(2\right) \]

Le calcul direct de I_{n} n’ayant pas l’air évident, on commence par établir une relation de récurrence d’ordre 2, vérifiée par la suite \left(I_{n}\right)_{n\in\mathbb{N}}. L’idée est de se débarrasser du dénominateur en combinant trois termes consécutifs de cette suite. Pour tout t\in\left[0,1\right] et pour tout n\in\mathbb{N} :

    \[ \frac{t^{n+2}+2t^{n+1}+t^{n}}{\left(t+1\right)^{2}}=\frac{t^{n}\left(t^{2}+2t+1\right)}{\left(t+1\right)^{2}}=t^{n} \]

et donc :

    \[ I_{n+2}+2I_{n+1}+I_{n}=\int_{0}^{1}t^{n}\thinspace dt=\frac{1}{n+1}\qquad\left({\spadesuit}\right) \]

Venons-en à la propriété annoncée dans l’encadré. On constate que :

    \[ I_{0}=\int_{0}^{1}\,\frac{1}{\left(t+1\right)^{2}}\,dt=\left[-\frac{1}{t+1}\right]_{0}^{1}=1-\frac{1}{2};\mbox{ soit : }\boxed{I_{0}=\frac{1}{2}} \]

et

    \[ I_{1}=\int_{0}^{1}\,\frac{t}{\left(t+1\right)^{2}}\,dt=\int_{0}^{1}\,\frac{\left(t+1\right)-1}{\left(t+1\right)^{2}}\,dt=\int_{0}^{1}\,\frac{1}{t+1}\,dt-I_{0};\mbox{ soit : }\boxed{I_{1}=\ln\left(2\right)-\frac{1}{2}} \]

Supposons maintenant que, pour un certain entier n\in\mathbb{N}, les nombres réels I_{n} et I_{n+1} s’expriment l’un et l’autre comme combinaisons à coefficients rationnels de 1 et \ln\left(2\right).

Alors, d’après \left(\spadesuit\right), il en va de même pour I_{n+2} :

    \begin{eqnarray*} I_{n+2} & = & \frac{1}{n+1}-2\left(a_{n+1}+b_{n+1}\ln\left(2\right)\right)-\left(a_{n}+b_{n}\ln\left(2\right)\right)\\ & = & \left(\frac{1}{n+1}-2a_{n+1}-a_{n}\right)+\left(-2b_{n+1}-b_{n}\right)\ln\left(2\right)\\ & = & a_{n+2}+b_{n+2}\ln\left(2\right) \end{eqnarray*}

avec :

    \[ \left\{ \begin{array}{ccc} a_{n+2} & = & \frac{1}{n+1}-2a_{n+1}-a_{n}\in\mathbb{Q}\\ \\ b_{n+2} & = & -2b_{n+1}-b_{n}\in\mathbb{Q} \end{array}\right. \]

Remarque :

La preuve par récurrence qui précède ne constitue pas la seule façon d’atteindre la conclusion. Si l’on sait décomposer une fraction rationnelle en éléments simples,  on écrit pour tout n\in\mathbb{N} :

    \[ \frac{X^{n}}{\left(X+1\right)^{2}}=P_{n}+\frac{\alpha_{n}}{X+1}+\frac{\beta_{n}}{\left(X+1\right)^{2}} \]

avec \left(\alpha_{n},\beta_{n}\right)\in\mathbb{Q}^{2} et P_{n}\in\mathbb{Q}\left[X\right], ce qui donne aussitôt la réponse, après intégration sur \left[0,1\right].

 

6 – Deux exemples plus sérieux

– Exemple A –

Considérons deux nombres réels a,b tels que a^{2}-4b>0 et soient \alpha,\beta les solutions (réelles) de l’équation du second degré r^{2}+ar+b=0. On sait que \alpha\neq\beta.On définit une famille de suites réelles par la relation de récurrence :

    \[ \forall n\in\mathbb{N},\thinspace u_{n+2}+a\thinspace u_{n+1}+b\thinspace u_{n}=0 \]

La donnée des deux premiers termes u_{0} et u_{1} identifie alors une suite réelle et une seule.

Comment exprimer u_{n} de manière explicite en fonction de u_{0}, u_{1} et n, pour tout n\in\mathbb{N} ?

Avec un peu d’algèbre linéaire, on peut parvenir de façon “naturelle” à cet objectif. Mais nous allons couper court et démontrer de façon rapide qu’il existe des réels \lambda,\mu tels que, pour tout n\in\mathbb{N} :

    \[ u_{n}=\lambda\alpha^{n}+\mu\beta^{n} \]

On commence par déterminer \lambda et \mu de telle sorte que l’égalité ci-dessus soit vraie aux rangs 0 et 1, autrement dit que :

    \[ \left\{ \begin{array}{ccc} \lambda+\mu & = & u_{0}\\ \lambda\alpha+\mu\beta & = & u_{1} \end{array}\right. \]

Ce système de Cramer se résout immédiatement pour donner :

    \[ \lambda=\frac{\beta u_{0}-u_{1}}{\beta-\alpha}\qquad\text{et}\qquad\mu=\frac{u_{1}-\alpha u_{0}}{\beta-\alpha} \]

Désormais, \lambda et \mu étant ainsi définis, on suppose que pour un certain n\in\mathbb{N} :

    \[ u_{n}=\lambda\alpha^{n}+\mu\beta^{n}\qquad\text{et}\qquad u_{n+1}=\lambda\alpha^{n+1}+\mu\beta^{n+1} \]

Alors :

    \[ u_{n+2}=-au_{n+1}-bu_{n}=-a\left(\lambda\alpha^{n+1}+\mu\beta^{n+1}\right)-b\left(\lambda\alpha^{n}+\mu\beta^{n}\right) \]

et donc :

    \[ u_{n+2}=-\lambda\alpha^{n}\left(a\alpha+b\right)-\mu\beta^{n}\left(a\beta+b\right) \]

Mais on ne perd pas de vue que \alpha,\beta sont solutions de l’équation r^{2}+ar+b=0; ce qui permet de remplacer dans l’expression précédente a\alpha+b par -\alpha^{2} et, de même, a\beta+b par -\beta^{2}. Au final :

    \[ u_{n+2}=\left(-\lambda\alpha^{n}\right)\left(-\alpha^{2}\right)+\left(-\mu\beta^{n}\right)\left(-\beta^{2}\right)=\lambda\alpha^{n+2}+\mu\beta^{n+2} \]

comme souhaité.

Remarque :

En appliquant ce qui précède à la célèbre suite de Fibonacci (voir au début de la section 5 pour sa définition), on voit qu’il existe des réels \lambda,\mu tels que :

    \[ \forall n\in\mathbb{N},\thinspace F_{n}=\lambda\left(\frac{1+\sqrt{5}}{2}\right)^{n}+\mu\left(\frac{1-\sqrt{5}}{2}\right)^{n} \]

Comme F_{0}=0 et F_{1}=1, on vérifie (en résolvant donc un petit système) que \lambda=-\mu=\frac{1}{\sqrt{5}}. Bref :

    \[ \boxed{\forall n\in\mathbb{N},\:F_{n}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right]} \]

– Exemple B –

Les célèbres “polynômes de Tchebytchev” (de première espèce) peuvent être mis en évidence via une récurrence du second ordre.

Prouvons qu’il existe, pour chaque n\in\mathbb{N}, une unique fonction polynôme T_{n} à coefficients entiers telle que :

    \[ \forall x\in\mathbb{R},\thinspace\cos\left(nx\right)=T_{n}\left(\cos\left(x\right)\right) \]

Traitons d’emblée la question de l’unicité. S’il existe, pour un certain n\in\mathbb{N}, deux fonctions polynômes P et Q vérifiant :

    \[ \forall x\in\mathbb{R},\thinspace\cos\left(nx\right)=P\left(\cos\left(x\right)\right)\qquad\text{et}\qquad\forall x\in\mathbb{R},\thinspace\cos\left(nx\right)=Q\left(\cos\left(x\right)\right) \]

alors :

    \[ \forall t\in\left[-1,1\right],\thinspace P\left(t\right)=Q\left(t\right) \]

ce qui prouve que P=Q car deux fonctions polynômes qui coïncident sur une partie infinie de \mathbb{R} (en l’occurrence, le segment \left[-1,1\right]) sont égales.

Pour l’existence, on raisonne par récurrence.

Aucun problème pour l’initialisation avec n=0 et n=1; il est évident que T_{0}:x\mapsto1 et T_{1}:x\mapsto x conviennent.

Supposons, pour un certain n\geqslant1, l’existence de fonctions polynômes à coefficients entiers T_{n-1} et T_{n} vérifiant la propriété. Alors, pour tout x\in\mathbb{R} :

    \begin{eqnarray*} \cos\left(\left(n+1\right)x\right) & = & 2\cos\left(x\right)\cos\left(nx\right)-\cos\left(\left(n-1\right)x\right)\\ & = & 2\cos\left(x\right)T_{n}\left(\cos\left(x\right)\right)-T_{n-1}\left(\cos\left(x\right)\right)\\ & = & T_{n+1}\left(\cos\left(x\right)\right) \end{eqnarray*}

à condition de poser T_{n+1}:x\mapsto2xT_{n}\left(x\right)-T_{n-1}\left(x\right).

Manifestement T_{n} est encore polynomiale et à coefficients entiers.

Voir l’exercice n° 6 de la fiche 01 sur la récurrence pour un résultat analogue (polynômes de Tchebytchev de deuxième espèce).

 

7 – Récurrences finies

Principe

Considérons un entier N\geqslant1 ainsi qu’un énoncé E_{n} portant sur un entier naturel n. Supposons que :

E_{0} est vrai,

• Pour tout n\in\left\{ 0,\cdots,N-1\right\} , si E_{n} est vrai
alors E_{n+1} est aussi vrai.

Dans ces conditions, E_{n} est vrai pour tout n\in\left\{ 0,\cdots,N\right\}.

D’après l’inégalité de Bernoulli (voir l’exercice n° 2 de la fiche récurrence – 01), on sait que si m,n sont deux entiers tels que n\geqslant1 et m\geqslant2, alors :

    \[ \left(1+\frac{1}{n}\right)^{m}>1+\frac{m}{n} \]

On va montrer ici que si 1\leqslant m\leqslant n, alors :

    \[ \left(1+\frac{1}{n}\right)^{m}<1+\frac{m}{n}+\left(\frac{m}{n}\right)^{2} \]

Pour cela, fixons n et effectuons une récurrence (finie) sur m.

Pour m=1, c’est clair ! Et si l’inégalité est vraie pour un certain entier m tel que 1\leqslant m<n, alors :

    \[ \left(1+\frac{1}{n}\right)^{m+1}<\left(1+\frac{m}{n}+\frac{m^{2}}{n^{2}}\right)\left(1+\frac{1}{n}\right)=1+\frac{m+1}{n}+\frac{m+m^{2}}{n^{2}}+\frac{m^{2}}{n^{3}} \]

Mais :

    \[ \left(\frac{m+1}{n}\right)^{2}-\frac{m+m^{2}}{n^{2}}-\frac{m^{2}}{n^{3}}=\frac{m+1}{n^{2}}-\frac{m^{2}}{n^{3}}=\frac{mn+n-m^{2}}{n^{3}}>\frac{m}{n^{3}}>0 \]

de sorte qu’on obtient bien :

    \[ \left(1+\frac{1}{n}\right)^{m+1}<1+\frac{m+1}{n}+\frac{\left(m+1\right)^{2}}{n^{2}} \]

 

8 – Récurrences fortes

Principe

Considérons un énoncé E_{n} portant sur un entier naturel n et supposons que :

E_{0} est vrai,

• Pour tout n\in\mathbb{N}, si E_{k} est vrai pour tout k\in\left\{ 0,\cdots,n\right\} ,
alors E_{n+1} est aussi vrai.

Dans ces conditions, E_{n} est vrai pour tout n.

Tout comme pour les récurrences du second ordre, ceci découle du principe de récurrence standard, appliqué à l’énoncé G_{n} suivant : “E_{k} est vrai pour tout k\in\left\{ 0,\cdots,n\right\}“.

Un exemple à la fois simple et fondamental de récurrence forte ? La preuve de l’existence de diviseurs premiers.

De façon précise, on prouve que tout entier n\geqslant2 possède au moins un diviseur premier. C’est bien le cas pour n=2 (initialisation).

Pour l’hérédité, on suppose que pour un certain n\geqslant2 et pour tout k\in\left\{ 2,\cdots,n\right\} , l’entier k possède au moins un diviseur premier. On s’intéresse alors à n+1 : si cet entier est premier, c’est réglé et sinon il possède un diviseur k tel que 2\leqslant k\leqslant n. L’hypothèse de récurrence montre que k possède un diviseur premier et donc n+1 aussi.

Dans les deux sections qui suivent, deux exemples beaucoup moins immédiats sont décortiqués.

 

9 – Nombres harmoniques

Dans ce qui suit, on note H_{n} le n-ème nombre harmonique, défini par :

    \[ H_{n}=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}\qquad\text{pour tout }n\geqslant1 \]

Autrement dit, H_n est la n-ème somme partielle de la série harmonique.
Le calcul des premiers termes de la suite \left(H_{n}\right)_{n\geqslant1} conduit à :

    \[ H_{1}=1,\qquad H_{2}=\frac{3}{2},\qquad H_{3}=\frac{11}{6},\qquad H_{4}=\frac{25}{12},\qquad H_{5}=\frac{137}{60} \]

et un peu plus loin :

    \[ H_{10}=\frac{7\thinspace381}{2\thinspace520},\qquad H_{20}=\frac{55\thinspace835\thinspace135}{15\thinspace519\thinspace504},\qquad H_{30}=\frac{9\thinspace304\thinspace682\thinspace830\thinspace147}{2\thinspace329\thinspace089\thinspace562\thinspace800} \]

Toutes ces fractions sont écrites sous forme irréductible. Il semble que la suite des numérateurs augmente rapidement, tout comme celle des dénominateurs.

On peut montrer que la suite \left(H_{n}\right)_{n\geqslant1} diverge vers +\infty et, plus précisément, que :

    \[ H_{n}\sim\ln\left(n\right)\text{ lorsque }n\text{ tend vers }+\infty \]

ce qui signifie que :

    \[ \lim_{n\rightarrow\infty}\frac{H_{n}}{\ln\left(n\right)}=1 \]

Mais cette étude asymptotique ne sera pas détaillée ici. On va plutôt se poser une question de nature arithmétique :

Les nombres H_{n} sont évidemment tous rationnels. Mais certains d’entre-eux sont-ils entiers ?

Nous allons voir qu’à l’exception de H_{1} (qui vaut 1), aucun terme de cette suite n’est entier.

Voici l’angle d’attaque proposé :

Etant donnés deux entiers naturels non nuls a et b, on ne peut pas décider si le nombre rationnel r=a/b est entier ou non, en connaissant seulement les parités de a et de b,
sauf dans un cas : celui où a est impair et b est pair (auquel cas r n’est pas entier).

On va précisément montrer que, pour tout n\geqslant2, le n-ème nombre harmonique H_{n} peut s’écrire :

    \[ H_{n}=\frac{I}{P}\qquad\text{avec }I\text{ impair et }P\text{ pair} \]

Visiblement : H_{2}=\frac{3}{2} est de cette forme.

Supposons (HR) que, pour tout entier k tel que 2\leqslant k\leqslant n, on ait :

    \[ H_{k}=\frac{i_{k}}{p_{k}} \]

avec i_{k},\,p_{k}\in\mathbb{N}^{\star}, i_{k} impair et p_{k} pair (on entame donc bien une récurrence forte).

Alors :

    \[ H_{n+1}=H_{n}+\frac{1}{n+1}=\frac{p_{n}+\left(n+1\right)\,i_{n}}{\left(n+1\right)\,p_{n}} \]

ce qui permet de conclure immédiatement si n+1 est impair. En effet, \left(n+1\right)\,i_{n} est impair car c’est le produit de deux entiers impairs et donc le numérateur p_{n}+\left(n+1\right)\,i_{n} est impair, car c’est la somme de deux entiers de parités contraires. Quant au dénominateur \left(n+1\right)\,p_{n}, il est pair puisque p_{n} l’est.

Et si n+1 est pair, alors on observe, en posant n+1=2k, que :

    \[ H_{2k}=x+\frac{1}{2}y \]

avec :

    \[ x=1+\frac{1}{3}+\cdots+\frac{1}{2k-1}\qquad\text{et}\qquad y=H_{k} \]

Le rationnel x est de la forme a/i, avec i impair (on le voit en réduisant au même dénominateur). Par ailleurs, d’après l’hypothèse de récurrence, on peut écrire :

    \[ H_{k}=\frac{u}{v}\qquad\text{avec }u\text{ impair et }v\text{ pair} \]

Ainsi :

    \[ H_{2k}=\frac{a}{i}+\frac{u}{2v}=\frac{2av+iu}{2iv} \]

qui est bien de la forme I/P avec I impair et P pair : CQFD !!

10 – Une récurrence… à l’envers !

L’inégalité entre moyennes arithmétique et géométrique est un résultat important, qui fait partie du cortège des inégalités dites “usuelles”.

Soit n un entier supérieur ou égal à 2. Pour tout n-uplet \left(x_{1},\cdots,x_{n}\right)
de réels strictement positifs :

    \[ \sqrt[n]{x_{1}\cdots x_{n}}\leqslant\frac{1}{n}\left(x_{1}+\cdots+x_{n}\right)\qquad\left(\diamondsuit\right) \]

Dans le cas particulier où n=2, ce théorème dit que si x_{1}>0 et x_{2}>0, alors :

    \[ \sqrt{x_{1}x_{2}}\leqslant\frac{x_{1}+x_{2}}{2} \]

ce qui découle immédiatement du fait que \left(\sqrt{x_{1}}-\sqrt{x_{2}}\right)^{2}\geqslant0.

Pour n\geqslant2 quelconque, on voit généralement cette inégalité comme conséquence de la convexité de la fonction exponentielle (pour les détails, voir à la fin de cette section). Mais historiquement, ce n’est pas ainsi que la première démonstration a été obtenue.

On doit à Cauchy une très jolie preuve qui fonctionne un peu comme une récurrence, mais à l’envers. Elle repose sur le principe suivant :

On considère un énoncé E_{n}, satisfaisant aux deux hypothèses suivantes :
• pour tout n\geqslant2, si E_{n+1} est vrai alors E_{n} est aussi vrai,

• il existe une suite d’entiers \left(u_{n}\right)_{n\geqslant1} qui diverge vers +\infty et telle que E_{u_{n}} est vrai pour tout n\geqslant1.

Dans ces conditions, E_{n} est vrai pour tout n\geqslant2.

Le premier point justifie que l’on parle ici de “récurrence à l’envers”. Bien entendu, ce premier point est insuffisant, à lui seul, pour atteindre la conclusion.

Mais l’association des deux hypothèses fonctionne à merveille ! Intuitivement, pour prouver que E_{p} est vrai pour un certain p\geqslant2, on va d’abord invoquer le second point et trouver un entier q>p tel que E_{q} soit vrai; puis, grâce au premier point, “redescendre” de E_{q} à E_{p} (en q-p itérations).

La première étape consiste donc à vérifier que si l’inégalité \left(\diamondsuit\right) est vraie au rang n+1, alors elle est aussi vraie au rang n.

Et la seconde consistera ensuite à montrer que \left(\diamondsuit\right) est vraie au rang 2^{n}, pour tout n\geqslant1 (autrement dit, la suite \left(u_{n}\right)_{n\geqslant1} utilisée sera la suite géométrique \left(2^{n}\right)_{n\geqslant1}).

– ETAPE 1 –

On suppose ici que, pour un certain n\geqslant2 et pour tout \left(n+1\right)-uplet \left(x_{1},\cdots,x_{n},x_{n+1}\right) de réels strictement positifs, on a :

    \[ \left(x_{1}\cdots x_{n+1}\right)^{1/\left(n+1\right)}\leqslant\frac{1}{n+1}\left(x_{1}+\cdots+x_{n+1}\right)\qquad\left(\star\right) \]

Soient alors a_{1},\cdots,a_{n}>0. L’astuce consiste à écrire la moyenne géométrique de ces n réels comme celle de n+1 réels et d’appliquer l’hypothèse. Or justement, en raison de l’égalité :

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

on voit que :

    \[ \left(a_{1}\cdots a_{n}\right)^{1/n}=\left(a_{1}\cdots a_{n}\left(a_{1}\cdots a_{n}\right)^{1/n}\right)^{1/\left(n+1\right)} \]

et donc (d’après l’inégalité \left(\star\right) dans laquelle on a choisi x_{1}=a_{1},\cdots,x_{n}=a_{n} et x_{n+1}=\left(a_{1}\cdots a_{n}\right)^{1/n}) :

    \[ \left(a_{1}\cdots a_{n}\right)^{1/n}\leqslant\frac{1}{n+1}\left(a_{1}+\cdots+a_{n}+\left(a_{1}\cdots a_{n}\right)^{1/n}\right) \]

c’est-à-dire, après simplification :

    \[ \left(a_{1}\cdots a_{n}\right)^{1/n}\leqslant\frac{1}{n}\left(a_{1}+\cdots+a_{n}\right) \]

comme souhaité.

– ETAPE 2 –

On prouve ici, par une récurrence “standard”, que pour tout n\geqslant1 :

    \[ \left(x_{1}\cdots x_{2^{n}}\right)^{2^{-n}}\leqslant2^{-n}\left(x_{1}+\cdots+x_{2^{n}}\right)\qquad\left(\clubsuit\right) \]

pour tout 2^{n}-uplet \left(x_{1},\cdots,x_{2^{n}}\right) de réels strictement positifs. Pour n=1, c’est l’inégalité bien connue :

    \[ \sqrt{x_{1}x_{2}}\leqslant\frac{1}{2}\left(x_{1}+x_{2}\right) \]

déjà évoquée plus haut, juste après l’énoncé du théorème.

Supposons l’inégalité \left(\clubsuit\right) établie au rang n et soit x_{1},\cdots,x_{2^{n}},x_{2^{n}+1},\cdots,x_{2^{n+1}} une séquence de 2^{n+1} réels strictement positifs. On observe que :

    \[ \left(x_{1}\cdots x_{2^{n+1}}\right)^{2^{-\left(n+1\right)}}=\sqrt{\left(x_{1}\cdots x_{2^{n}}\right)^{2^{-n}}\left(x_{2^{n}+1}\cdots x_{2^{n+1}}\right)^{2^{-n}}} \]

donc, en utilisant le cas n=1, on voit déjà que :

    \[ \left(x_{1}\cdots x_{2^{n+1}}\right)^{2^{-\left(n+1\right)}}\leqslant\frac{1}{2}\left(\left(x_{1}\cdots x_{2^{n}}\right)^{2^{-n}}+\left(x_{2^{n}+1}\cdots x_{2^{n+1}}\right)^{2^{-n}}\right) \]

puis, en utilisant deux fois l’hypothèse de récurrence, on peut écrire séparément :

    \[ \left(x_{1}\cdots x_{2^{n}}\right)^{2^{-n}}\leqslant2^{-n}\left(x_{1}+\cdots+x_{2^{n}}\right) \]

et

    \[ \left(x_{2^{n}+1}\cdots x_{2^{n+1}}\right)^{2^{-n}}\leqslant2^{-n}\left(x_{2^{n}+1}+\cdots+x_{2^{n+1}}\right) \]

Ainsi :

    \[ \left(x_{1}\cdots x_{2^{n+1}}\right)^{2^{-\left(n+1\right)}}\leqslant2^{-\left(n+1\right)}\left(x_{1}+\cdots+x_{2^{n+1}}\right) \]

ce qui met un terme à l’étape 2, et donc à la preuve du théorème.

– Plus simplement –

Terminons cette section en donnant une preuve plus directe (ou moins alambiquée, comme on voudra), qui repose sur la convexité de la fonction exponentielle.

Rappelons qu’une fonction f définie sur un intervalle I et à valeurs dans \mathbb{R} est dite convexe lorsque “toute portion de son graphe est située en-dessous de la corde correspondante”, ce qui s’exprime de manière précise comme ceci :

\forall t\in\left[0,1\right],\thinspace\forall\left(x,y\right)\in I^{2},\thinspace f\left(\left(1-t\right)x+ty\right)\leqslant\left(1-t\right)\thinspace f\left(x\right)+t\thinspace f\left(y\right)

On démontre que si f est dérivable, alors sa convexité équivaut à la croissance de sa dérivée (et il en résulte aussitôt que, pour f deux fois dérivable, la convexité de f équivaut à la positivité de sa dérivée seconde).

Enfin, si f:I\rightarrow\mathbb{R} est convexe, alors (inégalité de Jensen discrète) pour tout entier n\geqslant2, pour tout \left(t_{1},\cdots,t_{n}\right)\in\left[0,1\right]^{n} tel que t_{1}+\cdots+t_{n}=1 et pour tout \left(x_{1},\cdots,x_{n}\right)\in I^{n} :

    \[ f\left(t_{1}x_{1}+\cdots+t_{n}x_{n}\right)\leqslant t_{1}\thinspace f\left(x_{1}\right)+\cdots+t_{n}\thinspace f\left(x_{n}\right) \]

Ces généralités étant rappelées, et vu que la fonction exponentielle est convexe, on a pour tout n\geqslant2 et pour tout n-uplet \left(x_{1},\cdots,x_{n}\right) de réels strictement positifs :

    \[ \exp\left(\frac{\ln\left(x_{1}\right)+\cdots+\ln\left(x_{n}\right)}{n}\right)\leqslant\frac{1}{n}\left(\exp\left(\ln\left(x_{1}\right)\right)+\cdots+\exp\left(\ln\left(x_{n}\right)\right)\right) \]

Autrement dit :

    \[ \boxed{\left(x_{1}\cdots x_{n}\right)^{1/n}\leqslant\frac{1}{n}\left(x_{1}+\cdots+x_{n}\right)} \]

 

11 – Erreur de raisonnement à la section 3 : explication

L’erreur réside dans le fait que si n=2, les points M_{2} et M_{n} sont confondus et ne définissent donc pas une droite !

Pour que cette prétendue preuve soit valide, encore eut-il fallu que l’on puisse initialiser la récurrence avec n=3, c’est qui est bien entendu impossible (on sait bien que trois points quelconques du plan n’ont aucune raison d’être alignés).


 

J’espère que ces quelques exemples de preuves par récurrence vous auront intéressé. D’autres sont disponibles sous la forme d’exercices. Merci de vos commentaires, qui comme toujours seront les bienvenus !

Partager cet article
  • 1
  •  
  •  
  •  
  •  

Laisser un commentaire

Fermer le menu