Problème — Les nombres de Catalan et leur série génératrice

Le plan. Une récurrence quadratique — chaque terme est une somme de produits de termes antérieurs — est exactement ce que le produit de Cauchy sait lire : elle se traduit en une équation du second degré sur la fonction génératrice. On résout, on écarte la mauvaise racine par continuité, on développe la racine carrée, et l'unicité des coefficients livre la formule close. Le rayon vient ensuite, gratuitement, de cette formule.

1) Les premières valeurs, et un rayon strictement positif.

Les valeurs. Avec $C_0=1$ : $$C_1=C_0{C}_0=1,C_2=C_0{C}_1+C_1{C}_0=2,C_3=C_0{C}_2+C_1{C}_1+C_2{C}_0=2+1+2=5,$$ $$C_4=C_0{C}_3+C_1{C}_2+C_2{C}_1+C_3{C}_0=5+2+2+5=14,$$ $$C_5=C_0{C}_4+C_1{C}_3+C_2{C}_2+C_3{C}_1+C_4{C}_0=14+5+4+5+14=42.$$ On reconnaît $1,1,2,5,14,42$.

La majoration. Montrons par récurrence forte que $C_n\le \frac{16^n}{(n+1{)}^2}$ pour tout $n\ge 0$.

Initialisation. $C_0=1$ et $\frac{16^0}{1^2}=1$ : vrai, avec égalité.

Hérédité. Supposons la majoration vraie pour tous les indices $\le n$. Alors $$C_{n+1}=\sum _{k=0}^n{C}_k{C}_{n-k}\le \sum _{k=0}^n\frac{16^k}{(k+1{)}^2}\cdot \frac{16^{n-k}}{(n-k+1{)}^2}=16^n{S}_n,S_n=\sum _{k=0}^n\frac{1}{(k+1{)}^2(n-k+1{)}^2}.$$ Majorons $S_n$. Posons $i=k+1$ et $j=n-k+1$, de sorte que $i,j\ge 1$ et $i+j=n+2$ ; alors $$S_n=\sum _{\begin{array}{c}i+j=n+2\\ i,j\ge 1\end{array}}\frac{1}{i^2{j}^2}.$$ Pour chaque couple, $\max (i,j)\ge \frac{n+2}{2}$, donc $\frac{1}{i^2{j}^2}=\frac{1}{\min (i,j{)}^2\max (i,j{)}^2}\le \frac{4}{(n+2{)}^2}\cdot \frac{1}{\min (i,j{)}^2}$. Chaque valeur $m$ du minimum est atteinte par au plus deux couples, d'où $$S_n\le \frac{8}{(n+2{)}^2}\sum _{m\ge 1}\frac{1}{m^2}\le \frac{8}{(n+2{)}^2}\left(1+\sum _{m\ge 2}\frac{1}{m(m-1)}\right)=\frac{8}{(n+2{)}^2}\cdot 2=\frac{16}{(n+2{)}^2},$$ la série télescopique ${\sum }_{m\ge 2}\left(\frac{1}{m-1}-\frac{1}{m}\right)$ valant $1$. Donc $$C_{n+1}\le 16^n\cdot \frac{16}{(n+2{)}^2}=\frac{16^{n+1}}{(n+2{)}^2},$$ ce qui achève la récurrence.

Le rayon. Avec $r=\frac{1}{16}$, on a $C_n{r}^n\le \frac{1}{(n+1{)}^2}\le 1$ : la suite $\left(C_n{r}^n\right)$ est bornée, donc $R\ge \frac{1}{16}>0$ (exercice 7, question 1).

(Une majoration grossière suffit ici : seul importe $R>0$, qui donne un intervalle sur lequel travailler. C'est la forme close de la question 4 qui livrera la valeur exacte du rayon.)

2) L'équation fonctionnelle. Pour $|x|<R$, la série $\sum C_n{x}^n$ converge absolument : son produit de Cauchy par elle-même converge donc, et sa somme vaut $f(x{)}^2$. Le terme général de ce produit est $$\sum _{k=0}^n{C}_k{x}^k{C}_{n-k}{x}^{n-k}=\left(\sum _{k=0}^n{C}_k{C}_{n-k}\right)x^n=C_{n+1}{x}^n,$$ par la définition même de la suite. Donc $$f(x{)}^2=\sum _{n\ge 0}{C}_{n+1}{x}^n.$$ En multipliant par $x$ et en décalant l'indice : $$xf(x{)}^2=\sum _{n\ge 0}{C}_{n+1}{x}^{n+1}=\sum _{m\ge 1}{C}_m{x}^m=f(x)-C_0=f(x)-1.$$ D'où, pour tout $|x|<R$, $$xf(x{)}^2-f(x)+1=0.$$ La récurrence quadratique est devenue une équation algébrique du second degré sur la fonction.

3) La résolution, et la racine parasite. Pour $x\ne 0$ fixé dans $]-R,R[$, le nombre $f(x)$ est racine du trinôme $x{T}^2-T+1$, de discriminant $1-4x$. Comme $R\le \frac{1}{4}$ n'est pas encore connu, remarquons simplement que $R\ge \frac{1}{16}$ et travaillons sur $\left]-\frac{1}{16},\frac{1}{16}\right[$, où $1-4x>0$ : les deux racines sont $$g_{\pm }(x)=\frac{1\pm \sqrt{1-4x}}{2x},$$ et elles sont distinctes puisque $\sqrt{1-4x}\ne 0$.

Écarter la racine « plus ». La fonction $f$ est continue en $0$, avec $f(0)=C_0=1$ : elle est donc bornée au voisinage de $0$. Or, quand $x\to 0^{+}$, le numérateur de $g_{+}$ tend vers $2$ et son dénominateur vers $0^{+}$, donc $g_{+}(x)\to +\infty$ ; et quand $x\to 0^{-}$, $g_{+}(x)\to -\infty$. La fonction $g_{+}$ n'est donc pas bornée au voisinage de $0$, et pour $|x|$ assez petit et non nul, $f(x)\ne g_{+}(x)$, donc $f(x)=g_{-}(x)$.

Sur tout l'intervalle. Sur chacun des deux intervalles $\left]-\frac{1}{16},0\right[$ et $\left]0,\frac{1}{16}\right[$, qui sont connexes par arcs, les ensembles $\{f=g_{-}\}$ et $\{f=g_{+}\}$ sont fermés relativement, disjoints — les deux racines étant distinctes — et de réunion l'intervalle : l'un des deux est vide. Comme $f=g_{-}$ au voisinage de $0$ de chaque côté, c'est $\{f=g_{+}\}$. Finalement $$f(x)=\frac{1-\sqrt{1-4x}}{2x}\text{pour }0<|x|<R.$$ (Cohérence en $0$ : $\sqrt{1-4x}=1-2x+O(x^2)$, donc le numérateur vaut $2x+O(x^2)$ et le quotient tend vers $1=f(0)$.)

4) Le développement, et la formule close. Par l'exercice 9 avec $\alpha =\frac{1}{2}$, $$\sqrt{1+u}=1+\sum _{n\ge 1}\frac{(-1{)}^{n-1}(2n-2)!}{2^{2n-1}n!(n-1)!}{u}^n(|u|<1).$$ Substituons $u=-4x$, licite pour $|x|<\frac{1}{4}$ — et en particulier sur $]-R,R[$ tant que $R\le \frac{1}{4}$, ce que la suite confirmera ; on travaille de toute façon sur $\left]-\frac{1}{16},\frac{1}{16}\right[$. Le terme d'indice $n$ devient $$\frac{(-1{)}^{n-1}(2n-2)!}{2^{2n-1}n!(n-1)!}(-4{)}^n{x}^n=\frac{(-1{)}^{2n-1}(2n-2)!2^{2n}}{2^{2n-1}n!(n-1)!}{x}^n=-\frac{2(2n-2)!}{n!(n-1)!}{x}^n,$$ puisque $(-1{)}^{n-1}(-1{)}^n=(-1{)}^{2n-1}=-1$ et $4^n=2^{2n}$. Donc $$\sqrt{1-4x}=1-\sum _{n\ge 1}\frac{2(2n-2)!}{n!(n-1)!}{x}^n,\text{puis}1-\sqrt{1-4x}=\sum _{n\ge 1}\frac{2(2n-2)!}{n!(n-1)!}{x}^n.$$ En divisant par $2x$ et en posant $m=n-1$ : $$f(x)=\frac{1-\sqrt{1-4x}}{2x}=\sum _{n\ge 1}\frac{(2n-2)!}{n!(n-1)!}{x}^{n-1}=\sum _{m\ge 0}\frac{(2m)!}{(m+1)!m!}{x}^m.$$ Deux séries entières de rayons strictement positifs ont la même somme sur un voisinage de $0$ : par unicité des coefficients (exercice 8), $$\boxed{C_m=\frac{(2m)!}{(m+1)!m!}=\frac{1}{m+1}\left(\genfrac{}{}{0ex}{}{2m}{m}\right).}$$ Contrôle. $m=0$ : $\frac{0!}{1!0!}=1$. $m=1$ : $\frac{2!}{2!1!}=1$. $m=2$ : $\frac{4!}{3!2!}=\frac{24}{12}=2$. $m=3$ : $\frac{6!}{4!3!}=\frac{720}{144}=5$. $m=4$ : $\frac{8!}{5!4!}=\frac{40320}{2880}=14$. $m=5$ : $\frac{10!}{6!5!}=\frac{3628800}{86400}=42$. La formule redonne exactement les six valeurs de la question 1.

Le rayon exact. Tous les $C_m$ sont strictement positifs, et $$\frac{C_{m+1}}{C_m}=\frac{(2m+2)!}{(m+2)!(m+1)!}\cdot \frac{(m+1)!m!}{(2m)!}=\frac{(2m+2)(2m+1)m!}{(m+2)!}=\frac{(2m+2)(2m+1)}{(m+2)(m+1)}=\frac{2(2m+1)}{m+2}⟶4.$$ Par la règle de d'Alembert appliquée aux coefficients, $R=\frac{1}{4}$ exactement.

5) L'asymptotique, par Stirling. Le problème du TD 5 a établi $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)\sim \frac{4^n}{\sqrt{\pi n}}$. Donc $$C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)\sim \frac{1}{n}\cdot \frac{4^n}{\sqrt{\pi n}}=\frac{4^n}{\sqrt{\pi }{n}^{3/2}},$$ en utilisant $n+1\sim n$. Par conséquent $$\frac{C_n}{4^n}\sim \frac{1}{\sqrt{\pi }{n}^{3/2}},$$ terme général d'une série de Riemann d'exposant $\frac{3}{2}>1$ : $\sum C_n{4}^{-n}$ converge. (Au passage, ${\left|C_n\right|}^{1/n}\to 4$, ce qui redonne $R=\frac{1}{4}$.)

Le contraste. Le TD 5 a montré que $\sum \left(\genfrac{}{}{0ex}{}{2n}{n}\right)4^{-n}$ diverge, son terme général étant équivalent à $\frac{1}{\sqrt{\pi n}}$, exposant $\frac{1}{2}\le 1$. C'est le seul facteur $\frac{1}{n+1}$ qui fait passer l'exposant de $\frac{1}{2}$ à $\frac{3}{2}$, c'est-à-dire qui fait basculer la nature de la série. Au bord du disque de convergence, tout se joue sur un facteur polynomial.

6) Le bord, par Abel radial. Le théorème d'Abel radial — au programme, sa démonstration seule étant hors programme — affirme : si $\sum a_n{\rho }^n$ converge, où $\rho >0$, alors $\sum a_n{x}^n\to \sum a_n{\rho }^n$ quand $x\to {\rho }^{-}$. Ici $\rho =\frac{1}{4}$ et $\sum C_n{4}^{-n}$ converge par la question 5 : le théorème s'applique, et $$\sum _{n\ge 0}\frac{C_n}{4^n}=\underset{x\to {\frac{1}{4}}^{-}}{\lim }f(x).$$ Or, par la forme close de la question 3, $$f(x)=\frac{1-\sqrt{1-4x}}{2x}\underset{x\to {\frac{1}{4}}^{-}}{\to }\frac{1-0}{2\cdot \frac{1}{4}}=\frac{1}{1/2}=2.$$ Donc $$\sum _{n\ge 0}\frac{C_n}{4^n}=2.$$ Contrôle numérique. Les onze premiers termes donnent $1+0,25+0,125+0,078125+0,0546875+0,041016+0,032227+0,026184+0,021820+0,018547+0,016018=1,66362$. La convergence est lente, comme l'annonce le reste : par la question 5, il est équivalent à ${\sum }_{k>n}\frac{1}{\sqrt{\pi }{k}^{3/2}}\sim \frac{2}{\sqrt{\pi n}}$, qui vaut $0,357$ pour $n=10$ — et $1,664+0,357=2,02$, cohérent avec la valeur $2$.

Les deux mécanismes du chapitre. Une récurrence linéaire à coefficients constants — $F_{n+2}=F_{n+1}+F_n$ pour Fibonacci, la même pour les nombres de Lucas — donne une équation linéaire sur la série génératrice : la somme est une fraction rationnelle, $\frac{x}{1-x-x^2}$, et les éléments simples livrent la formule close. Une récurrence quadratique donne une équation du second degré : la somme est une fonction algébrique, $\frac{1-\sqrt{1-4x}}{2x}$, et c'est le développement de $(1+u{)}^{1/2}$ qui livre la formule close. Dans les deux cas, le mouvement est le même : une récurrence sur des nombres devient une équation sur une fonction, et l'unicité des coefficients rapatrie la solution vers les nombres.

Ce que le problème installe. La méthode des fonctions génératrices, dans sa version la plus démonstrative : traduire, résoudre, redescendre. Et l'usage précis des trois outils du chapitre — le produit de Cauchy, qui lit une convolution ; l'unicité des coefficients, qui autorise l'identification ; le théorème d'Abel radial, qui permet d'aller jusqu'au bord du disque, là où la dérivation et le produit de Cauchy n'ont plus cours. Enfin, un rappel de dépendance : la seule chose empruntée hors du chapitre est la formule de Stirling, établie au TD précédent — un aller simple, dans le bon sens.