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 accompagnée de quelques exemples simples.

Pour l’essentiel, on y a expliqué qu’é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 pas démontré…

Une preuve rigoureuse, lorsque $N=0$ , fait l’objet de la première section du présent article.

Le cas général est analogue.

1 – Le principe de récurrence « classique »

On utilisera dans ce qui suit la propriété fondamentale suivante :

Proposition

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}$ .

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}$ .

Aux exemples de preuves par récurrence présentés dans l’article Qu’est-ce qu’une preuve par récurrence, je propose d’ajouter le suivant, que je trouve particulièrement é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 ? Cette opération est-elle encore possible ?

Evidemment non, puisqu’il reste 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.

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.

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é !

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 est donnée 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 aux rangs 0 et 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 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}}$

$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{equation*}\begin{split}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{split}\end{equation*}$

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],$ .
Ceci 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 les rangs 0 et 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{equation*}\begin{split}\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{split}\end{equation*}$

à 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

Proposition

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\llbracket0,N-1\rrbracket,$ si $E_{n}$ est vrai, alors $E_{n+1}$ est aussi vrai.

Dans ces conditions, $E_{n}$ est vrai pour tout $n\in\llbracket0,N\rrbracket$ .

Voici un exemple d’utilisation.

Inégalité de type Bernoulli

Un cas particulier de la très classique inégalité de Bernoulli (voir l’exercice n° 2 de la fiche récurrence – 01), nous dit 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\llbracket0,n\rrbracket$ 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\llbracket0,n\rrbracket$ « .

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\llbracket2,n\rrbracket$ 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 h armonique.
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 soulever une question de nature arithmétique :

Question

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 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}H_k$

avec :

$x=1+\frac{1}{3}+\cdots+\frac{1}{2k-1}$

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

Théorème

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 :

Principe

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 $\left(u_{n}\right)_{n\geqslant1}$ d’entiers naturels :

qui diverge vers $+\infty$
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 (cliquer pour déplier / replier)

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 :

$\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 (cliquer pour déplier / replier)

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)$

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

Une preuve plus simple (cliquer pour déplier / replier)

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 », comme on le comprend sur l’illustration ci-contre.

La version formalisée de cette définition est :

$\boxed{\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 peut montrer 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)}$

L’inégalité voulue est ainsi établie.

11 – Retour sur un raisonnement invalide

A la section 3, nous avons présenté un résultat manifestement faux.

L’erreur résidait 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 ne sont en général pas alignés).

Vos questions ou remarques sont 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 11 Sep 2022 Répondre

Ça ne passe toujours pas. L’exercice illustratif (qui utilise une récurrence descendante forte) concernait la fonction de 91 de Mac Carthy que l’on trouve par exemple sur Wikipedia 🙂
Oncle Junior 11 Sep 2022 Répondre

***Quelques mots ne sont pas passés ! Je remets le paragraphe sans omission:
– Une variante parfois utile est la récurrence descendante: si E(N) est vrai, et si E(n) vrai entraîne E(n-1) vrai pour tout n entier relatif <=N, alors E(n) est vrai pour tout n entier relatif 100, et f(f(n+11)) pour n<=100, montrer que pour tout n<=101: f(n)=91.
Oncle Junior 8 Sep 2022 Répondre

Bonjour Monsieur,
Merci pour cet article généreux 🙂

Quelques petites remarques de forme:
-Partie 2: au début, dans la marge de droite, la figure présentant un trimino ne s’affiche pas;
-Partie 7: la phrase « dans ces conditions… » qui suit la proposition devait probablement être incluse dans l’encadré de couleur matérialisant la proposition;
-Partie 7: un peu plus bas, le lien renvoyant vers la fiche récurrence ne semble plus actif;
-Partie 10: dans la deuxième flèche du principe, il est possible d’ajouter que la suite (u(n)) est constituée d’entiers naturels « supérieurs ou égaux à 2 » afin que l’énoncé Eu(n) ait toujours un sens.

Quelques commentaires pour les autres lecteurs intéressés, ou vous-même si vous souhaitez rebondir sur certains d’entre eux:
-La récurrence du second ordre a été présentée dans la partie 4. On peut également utiliser des récurrences de tout ordre k supérieur ou égal à 3. Par exemple pour le cas du troisième ordre et pour des énoncés E(n) sur les entiers naturels n, l’initialisation consistera à montrer que E(0) E(1) et E(2) sont vrais, tandis que pour l’hérédité il faudra montrer que E(n) E(n+1) et E(n+2) vrais entraînent E(n+3) vrai;
-La démonstration de l’exemple A de la partie 6 qui fournit l’existence de lambda et mu, assure également l’unicité de ces deux réels;
-Une variante parfois utile est la récurrence descendante: si E(N) vrai, et si E(n) vrai entraîne E(n-1) vrai pour tout n entier relatif <=N, alors E(n) est vrai pour tout n entier relatif 100, et f(f(n+11)) pour n<=100, montrer que pour tout n<=101 on a f(n)=91;
-La récursivité, notion très utilisée en informatique, fait penser au raisonnement par récurrence;
-J'ai aperçu dans un devoir de prépa des "définitions et démonstrations par induction structurelle", et cela avait l'air proche de la notion de récurrence et intéressant ! ;
-Dans le même genre que le point précédent, toujours dans un devoir de prépa, il était présenté la notion de "récurrence transfinie sur un ensemble bien ordonné".

Enfin, si vous le voulez bien, plus tard lorsque vous aurez le temps pour cela, je me permets d’insister sur mon dernier commentaire présent à la suite de l'article « Négation, contraposée, réciproque », car je sens que vous aurez certainement des livres de qualité à conseiller aux lecteurs du site !

Bien à vous