Renforcer l'hypothèse de récurrence

Ce qu'on a le droit d'utiliser. Le principe de récurrence, et la relation entre deux termes consécutifs, le $(n+1)$-ième facteur étant $\frac{2(n+1)-1}{2(n+1)}$ : $$P_{n+1}=P_n\times \frac{2n+1}{2n+2}.$$ Deux réels strictement positifs se comparent par leurs carrés. Notons ${\mathcal{H}}_n$ l'assertion « $P_n<\frac{1}{\sqrt{3n}}$ » et ${\mathcal{K}}_n$ l'assertion « $P_n\le \frac{1}{\sqrt{3n+1}}$ ».

a) L'échec de la récurrence directe.

Initialisation. $P_1=\frac{1}{2}$, et $\frac{1}{2}<\frac{1}{\sqrt{3}}$ puisque $\sqrt{3}<2$ (car $3<4$) : ${\mathcal{H}}_1$ est vraie.

Tentative d'hérédité. Soit $n\ge 1$ tel que ${\mathcal{H}}_n$ soit vraie. En multipliant l'inégalité stricte $P_n<\frac{1}{\sqrt{3n}}$ par le réel strictement positif $\frac{2n+1}{2n+2}$, on obtient $$P_{n+1}<M_n,\text{ouˋ}{M}_n=\frac{2n+1}{(2n+2)\sqrt{3n}}.$$ C'est tout ce que l'hypothèse fournit ; pour conclure ${\mathcal{H}}_{n+1}$, il faudrait $M_n\le \frac{1}{\sqrt{3n+3}}$. Comparons les carrés : $$M_n^2>\frac{1}{3n+3}⟺(2n+1{)}^2(3n+3)>(2n+2{)}^2\cdot 3n,$$ en chassant les dénominateurs, qui sont strictement positifs. Développons les deux membres : $$(2n+1{)}^2(3n+3)=(4n^2+4n+1)(3n+3)=12n^3+24n^2+15n+3,$$ $$(2n+2{)}^2\cdot 3n=(4n^2+8n+4)\cdot 3n=12n^3+24n^2+12n.$$ La différence vaut $3n+3$, strictement positive : pour tout $n\ge 1$, le majorant $M_n$ est strictement au-dessus de la cible $\frac{1}{\sqrt{3(n+1)}}$.

Pourquoi l'hérédité ne se referme pas. L'hypothèse dit que $P_n$ est sous $\frac{1}{\sqrt{3n}}$, mais pas de combien : un réel sous cette borne, mais très près d'elle, donnerait après multiplication un nombre très proche de $M_n$, donc au-dessus de la cible. On ne peut pas déduire ${\mathcal{H}}_{n+1}$ de ${\mathcal{H}}_n$, et ce à tout rang : il manque toujours la marge $3n+3$. L'inégalité ${\mathcal{H}}_n$ est pourtant vraie — on va le prouver — mais trop faible pour se transmettre d'un rang au suivant.

b) La récurrence renforcée. L'assertion ${\mathcal{K}}_n$ est plus forte que ${\mathcal{H}}_n$, puisque $\frac{1}{\sqrt{3n+1}}<\frac{1}{\sqrt{3n}}$ ; on va pourtant la démontrer, précisément parce qu'elle porte sa propre marge.

Initialisation. $P_1=\frac{1}{2}$ et $\frac{1}{\sqrt{3+1}}=\frac{1}{2}$ : ${\mathcal{K}}_1$ est vraie, avec égalité.

Hérédité. Soit $n\ge 1$ tel que ${\mathcal{K}}_n$ soit vraie. En multipliant par $\frac{2n+1}{2n+2}>0$ : $$P_{n+1}\le \frac{2n+1}{(2n+2)\sqrt{3n+1}}.$$ Il suffit donc de montrer que ce majorant est au plus $\frac{1}{\sqrt{3n+4}}$, ce qui, en comparant les carrés et en chassant les dénominateurs positifs, s'écrit $$(2n+1{)}^2(3n+4)\le (2n+2{)}^2(3n+1).$$ Or $$(2n+1{)}^2(3n+4)=(4n^2+4n+1)(3n+4)=12n^3+28n^2+19n+4,$$ $$(2n+2{)}^2(3n+1)=(4n^2+8n+4)(3n+1)=12n^3+28n^2+20n+4.$$ La différence vaut $n\ge 0$ : l'inégalité est vraie. Donc $P_{n+1}\le \frac{1}{\sqrt{3(n+1)+1}}$ : ${\mathcal{K}}_{n+1}$ est vraie.

Conclusion. Par récurrence, $P_n\le \frac{1}{\sqrt{3n+1}}<\frac{1}{\sqrt{3n}}$ pour tout $n\ge 1$ (la racine carrée est croissante, le passage à l'inverse renverse l'ordre). L'énoncé faible, que la récurrence directe ne savait pas prouver, découle de l'énoncé fort.

D'où vient le « plus un » ? Du calcul lui-même. Cherchons un énoncé $P_n\le \frac{1}{\sqrt{3n+c}}$, avec une constante $c$ à déterminer : la même comparaison des carrés conduit à la différence $$(2n+2{)}^2(3n+c)-(2n+1{)}^2(3n+3+c)=(4c-3)n+3(c-1).$$ Pour $c=0$, elle vaut $-3n-3$ : l'échec du a). Pour $c=1$, elle vaut $n$ : le succès du b). Et l'initialisation, $\frac{1}{2}\le \frac{1}{\sqrt{3+c}}$, impose $c\le 1$. On introduit un paramètre, et l'hérédité dit elle-même lequel choisir.

c) Les factorielles, et le coefficient binomial. Le dénominateur de $P_n$ est le produit des $n$ premiers pairs : $2\times 4\times \cdots \times (2n)=2^{n}n!$. Le numérateur, produit des $n$ premiers impairs, s'obtient en divisant $(2n)!$ par ce produit des pairs : $$1\times 3\times \cdots \times (2n-1)=\frac{1\times 2\times 3\times \cdots \times (2n)}{2\times 4\times \cdots \times (2n)}=\frac{(2n)!}{2^{n}n!}.$$ Donc $$P_n=\frac{(2n)!}{2^{n}n!\times 2^{n}n!}=\frac{(2n)!}{4^n(n!{)}^2}=\frac{1}{4^n}\left(\genfrac{}{}{0ex}{}{2n}{n}\right),$$ puisque le coefficient binomial « $n$ parmi $2n$ » vaut $\frac{(2n)!}{n!(2n-n)!}=\frac{(2n)!}{(n!{)}^2}$ (définition rappelée de la Terminale, et reprise au chapitre suivant). Le b) donne alors, en multipliant par $4^n>0$ : $$\left(\genfrac{}{}{0ex}{}{2n}{n}\right)=4^n{P}_n\le \frac{4^n}{\sqrt{3n+1}}.$$

Contrôle numérique. $P_2=\frac{3}{8}=0,375$ et $\frac{1}{\sqrt{7}}\approx 0,378$ : l'inégalité du b) est serrée. Pour $n=10$ : $\left(\genfrac{}{}{0ex}{}{20}{10}\right)=184756$ et $\frac{4^{10}}{\sqrt{31}}\approx 188330$. Un calcul exact vérifie ${\mathcal{K}}_n$ jusqu'à $n=2000$.

Ce que l'exercice installe. Le renforcement de l'hypothèse de récurrence est un réflexe de prépa : quand l'hérédité échoue faute de marge, on cherche un énoncé plus précis qui porte sa propre marge, au besoin par un paramètre que l'hérédité fixe. On le retrouvera pour les suites récurrentes et les majorations d'erreurs. Le nombre $P_n=\left(\genfrac{}{}{0ex}{}{2n}{n}\right)/4^n$ reviendra au chapitre des probabilités : c'est la probabilité d'obtenir exactement $n$ fois « pile » en $2n$ lancers d'une pièce équilibrée, et elle est donc au plus $\frac{1}{\sqrt{3n+1}}$. La séance suivante en donnera une minoration.