Une récurrence quadratique : les nombres de Catalan

La stratégie. Une récurrence non linéaire — le terme suivant est une somme de produits — n'a pas de formule de première année. Mais cette somme de produits est un produit de Cauchy : la fonction génératrice vérifie une équation du second degré. On raisonne par analyse-synthèse : l'analyse suppose un rayon non nul et trouve la seule fonction possible ; la synthèse part de cette fonction, la développe, et prouve que ses coefficients sont les $C_n$ — ce qui établit, au passage, que le rayon est non nul, sans aucune majoration a priori.

1) Les premiers termes. $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=5+2+2+5=14$ ; $C_5=14+5+4+5+14=42$.

2) L'analyse. Sur $]-R,R[$, la série converge absolument ; le produit de Cauchy de $f$ par elle-même donne $$f(x{)}^2=\sum _{n\ge 0}\left(\sum _{k=0}^n{C}_k{C}_{n-k}\right)x^n=\sum _{n\ge 0}{C}_{n+1}{x}^n.$$ En multipliant par $x$ : $xf(x{)}^2={\sum }_{n\ge 0}{C}_{n+1}{x}^{n+1}=f(x)-C_0=f(x)-1$. D'où $xf(x{)}^2-f(x)+1=0$ sur $]-R,R[$.

Le choix de la racine. Posons $r=\min \left(R,\frac{1}{4}\right)$ et $\phi (x)=2xf(x)-1$, continue sur $]-r,r[$. L'équation donne $$\phi (x{)}^2=4x\left(xf(x{)}^2-f(x)\right)+1=1-4x,$$ strictement positif sur $]-r,r[$ puisque $x<\frac{1}{4}$. La fonction continue $\phi$ ne s'annule donc pas sur l'intervalle $]-r,r[$ : par le théorème des valeurs intermédiaires, elle garde le signe de $\phi (0)=-1$. Ainsi $\phi (x)=-\sqrt{1-4x}$, et, pour $0<|x|<r$, $$f(x)=\frac{1-\sqrt{1-4x}}{2x}.$$ (L'autre racine, $\frac{1+\sqrt{1-4x}}{2x}$, n'est pas bornée au voisinage de $0$ : c'est la continuité en $0$ qui l'écarte.)

3) La synthèse : le développement. Pour $|u|<1$, le développement de $(1+u{)}^{\alpha }$ avec $\alpha =\frac{1}{2}$ s'écrit $(1+u{)}^{1/2}=1+{\sum }_{n\ge 1}{\beta }_n{u}^n$, où, pour $n\ge 1$, $${\beta }_n=\frac{\frac{1}{2}\left(\frac{1}{2}-1\right)\cdots \left(\frac{1}{2}-n+1\right)}{n!}=\frac{(-1{)}^{n-1}1\cdot 3\cdots (2n-3)}{2^{n}n!},$$ et $1\cdot 3\cdots (2n-3)=\frac{(2n-2)!}{2^{n-1}(n-1)!}$. En remplaçant $u$ par $-4x$, pour $|x|<\frac{1}{4}$, le coefficient de $x^n$ vaut ${\beta }_n(-4{)}^n=-\frac{2(2n-2)!}{n!(n-1)!}$ pour $n\ge 1$. Donc $$1-\sqrt{1-4x}=\sum _{n\ge 1}\frac{2(2n-2)!}{n!(n-1)!}{x}^n,$$ et, pour $0<|x|<\frac{1}{4}$, en divisant par $2x$ et en posant $m=n-1$, $$g(x)=\sum _{m\ge 0}\frac{(2m)!}{(m+1)!m!}{x}^m=\sum _{m\ge 0}\frac{1}{m+1}\left(\genfrac{}{}{0ex}{}{2m}{m}\right)x^m.$$ En $x=0$, la série vaut $1=g(0)$. $g$ est développable sur $\left]-\frac{1}{4},\frac{1}{4}\right[$, avec les coefficients annoncés.

4) La synthèse : l'identification. L'équation. Pour $x\ne 0$, avec $s=\sqrt{1-4x}$, $$xg(x{)}^2-g(x)+1=\frac{(1-s{)}^2-2(1-s)+4x}{4x}=\frac{s^2-1+4x}{4x}=0,$$ et en $x=0$ : $0-1+1=0$.

Le produit de Cauchy. Notons $c_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$. Sur $\left]-\frac{1}{4},\frac{1}{4}\right[$, $$xg(x{)}^2=\sum _{n\ge 0}\left(\sum _{k=0}^n{c}_k{c}_{n-k}\right)x^{n+1},g(x)-1=\sum _{n\ge 0}{c}_{n+1}{x}^{n+1}.$$ Ces deux séries entières ont la même somme sur un intervalle ouvert contenant $0$ : par unicité des coefficients, $c_{n+1}={\sum }_{k=0}^n{c}_k{c}_{n-k}$ pour tout $n$, et $c_0=1$.

La récurrence forte. Les suites $(c_n)$ et $(C_n)$ ont le même premier terme et la même relation, qui détermine chaque terme à partir des précédents : si $c_k=C_k$ pour $k\le n$, alors $c_{n+1}=\sum c_k{c}_{n-k}=\sum C_k{C}_{n-k}=C_{n+1}$. Donc $C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ pour tout $n$.

Le rayon. Il vaut au moins $\frac{1}{4}$ par la question 3, et le quotient $$\frac{C_{n+1}}{C_n}=\frac{(2n+2)(2n+1)}{(n+1{)}^2}\cdot \frac{n+1}{n+2}=\frac{2(2n+1)}{n+2}$$ tend vers $4$ : par la règle de d'Alembert, le rayon vaut exactement $\frac{1}{4}$. L'hypothèse de l'analyse était donc satisfaite, et $f=g$.

Le point délicat. L'analyse seule ne prouve rien : elle suppose le rayon non nul. Une majoration directe $C_n\le 4^n$ par récurrence forte ne passe pas — l'hérédité ne donne que $C_{n+1}\le (n+1)4^n$. La synthèse contourne l'obstacle : elle construit une série de rayon $\frac{1}{4}$ dont les coefficients vérifient la récurrence.

Contrôle numérique. La récurrence donne $1,1,2,5,14,42,132,429,1430$, et la formule $\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ les mêmes nombres. En $x=0,1$, $g(0,1)=\frac{1-\sqrt{0,6}}{0,2}=1,1270167$, valeur que redonne la série.

Ce que l'exercice installe. Une récurrence non linéaire devient une équation algébrique sur la fonction génératrice ; la continuité en $0$ choisit la racine ; l'analyse-synthèse et l'unicité des coefficients concluent. Les nombres de Catalan comptent les parenthésages d'un produit, les arbres binaires, les chemins qui ne passent jamais sous l'axe ; la racine carrée $\sqrt{1-4x}$ reviendra au TD 11, dans la marche aléatoire et son premier retour à l'origine.