Série génératrice

Soit $(a_n)$ une suite de nombres complexes. On appelle série génératrice associée à la suite la série formelle $$\sum_{n=0}^{+\infty}a_n X^n.$$

Les séries génératrices sont un outil puissant pour déterminer explicitement des suites que l'on ne connait que par les relations qu'elles vérifient qui les donnent implicitement. Voici un exemple, le calcul des nombres de Catalan. On note $a_n$ le nombre de parenthésages différents opérant sur deux facteurs adjacents du produit $a_1\cdots a_n$ :

La dernière multiplication que l'on effectue réalise le produit des $k$ premiers nombres par les $n-k$ derniers, pour $k$ allant de $1$ à $n-1$. On peut ensuite parenthéser de $a_k$ façons les $k$ premiers nombres, et de $n-k$ façons les $n-k$ derniers. La suite $(a_n)$ vérifie donc la relation de récurrence $$a_n=\sum_{k=1}^{n-1}a_k a_{n-k}$$ et cette relation de récurrence permet, connaissant $a_1=1$, de calculer successivement $a_2$, $a_3$,... Pour calculer directement la valeur de $a_n$ pour tout $n\geq 1$, on va commencer pas poser $a_0=0$ et écrire la relation de récurrence sous la forme $$a_n=\sum_{k=0}^{n}a_k a_{n-k}.$$ On note aussi $S(X)$ la série génératrice de $(a_n)$. Alors la relation de récurrence précédente permet d'écrire : \begin{align*} S(X)&=X+\sum_{n=2}^{+\infty}a_n X^n\\ &=X+\sum_{n=2}^{+\infty}\sum_{k=0}^n a_k a_{n-k}X^n\\ &=X+\left(\sum_{n=1}^{+\infty}a_n X^n\right)\left(\sum_{n=1}^{+\infty}a_n X^n\right)\\ &=X+S^2(X). \end{align*} Il vient donc $$S(X)=\frac{1-\sqrt{1-4X}}2.$$ En effectuant le développement en série formelle de $\sqrt{1-4X}$, on trouve la valeur exacte des coefficients $a_n$, à savoir $$a_n=\frac{\binom{2n-2}{n-1}}{n}.$$

On aurait bien sûr pu effectuer ces calculs avec des séries entières plutôt qu'avec des séries formelles, mais il aurait fallu s'assurer de la convergence.