4 Séries génératrices

4.1 Définition et rappels sur les séries

1. Définition : la série génératrice associée à la suite $\left(u_{n}\right)_{n\in \mathbb{N}}$ est, par définition, la série $Sg\left(z\right)=\sum _{n\in \mathbb{N}}u_{n}\, z^{n}$.
2. Commentaire. Dans cette définition $z$ est un nombre complexe, avec éventuellement une condition $\left\vert z\right\vert<k$ pour assurer la convergence. Tandis que la suite $u_{n}$ est à valeurs dans n'importe quelle algèbre sur $\mathbb{C}$. Par exemple $\mathbb{C}$ lui même, ou bien $\mathbb{C}\left[X\right]$ (les polynômes) ou bien ...
3. Définition. On appelle sommes partielles de la série $\sum v_{n}$ les nombres $s_{n}=\sum _{k=0}^{k=n}v_{k}$.
4. Théorème. Une série à termes positifs converge toujours, soit vers $+\infty$, soit vers un réel, qui est alors la borne supérieure des $s_{n}$.
   exo 72.  Montrer que $\sum \frac{1}{k^{2}}\rightarrow \frac{\pi ^{2}}{6}$.
5. Définition : maximum. Soit $X$ une partie non vide de $\mathbb{R}$. Un nombre $m$ vérifiant à la fois $m\in X$ et $X\leq m$, c'est à dire $\forall x\in X\, :\, x\leq m$ est appelé un maximum de $X$. Il est immédiat que le maximum est unique s'il existe.
6. Définition : borne supérieure. Soit $X$ une partie non vide de $\mathbb{R}$. Un nombre $\mu$ vérifiant à la fois $X\leq \mu$ et $\mu \leq M$ pour tout majorant $M$ de $X$ est appelé borne supérieure de $X$.
7. Propriétés. Il est immédiat que la borne supérieure est unique, et que le maximum lorsqu'il existe est aussi la borne supérieure.
8. Théorème. Toute partie non vide majorée de $\mathbb{R}$ admet une borne supérieure.

   exo 73.  Redémontrer cette propriété en construisant une suite croissante d'éléments $x_{n}\in X$ et une suite décroissante $M_{n}$ de majorants de $X$ de telle sorte que ces suites soient adjacentes (l'existence d'un $x_{0}$ et d'un $M_{0}$ sont données par l'hypothèse).

9. Théorème. Une série normalement convergente est convergente, c'est à dire : la convergence de la série $\sum \left\vert u_{n}\right\vert$ implique la convergence de $\sum u_{n}$. exo 74.  Redémontrer cette propriété en remarquant que $\left\vert s_{n+p}-s_{n}\right\vert\leq \sum _{k=n}^{k=n+p}\left\vert u_{k}\right\vert$ et en utilisant le critère de Cauchy.
10. La série harmonique. Par définition, $H_{n}=\sum _{1}^{n}\frac{1}{k}$. La propriété est que $H_{n}\rightarrow \infty$. exo 75.  Démontrer ce résultat en prouvant que $H_{2^{p}}>\left(p+1\right)/2$.
11. Série alternée. Il s'agit d'un cas tout à fait spécial de séries à termes réels, définie par $u_{n}$ décroît vers 0, i.e. $u_{n+1}\leq u_{n}$ et $u_{n}\rightarrow 0$. exo 76.  Démontrer que toute série alternée admet une limite $\lambda$, vérifiant en outre $\lambda \in \left[u_{n},\, u_{n+1}\right]$ pour tout $n$ (il est rappelé que la notation $\left[a,\, b\right]$ ne suppose pas que $a\leq b$). exo 77.  Quelle est la limite de la série harmonique alternée ?

4.2 Propriétés élémentaires des séries génératrices

1. Proposition. La série génératrice de la suite $n\mapsto 1$ est $S\left(z\right)=\frac{1}{1-z}$.
2. Proposition. La série génératrice de la suite $n\mapsto n$ est $S\left(z\right)=\frac{z}{\left(1-z\right)^{2}}$. exo 78.  Démontrer ce résultat par un développement limité de la série proposée.
3. Proposition. La série génératrice $S\left(u+v\right)\left(n\right)$ de la suite $n\mapsto u_{n}+v_{n}$ est la somme des séries génératrices des suites $n\mapsto u_{n}$ et $n\mapsto v_{n}$. Autrement dit :
   $$S\left(u+v\right)\left(z\right)=S\left(u\right)\left(z\right)+S\left(v\right)\left(z\right)$$

4. Proposition. Le produit des séries génératrices est la série génératrice de la convolution des deux suites, i.e. la série génératrice de la suite $n\mapsto w_{n}=\sum _{0}^{n}u_{k}\, v_{n-k}$ (cette règle est exactement celle que l'on applique pour le produit de deux polynômes). Autrement dit :
   $$S\left(u\star v\right)\left(z\right)=S\left(u\right)\left(z\right)\times S\left(v\right)\left(z\right)$$

5. Proposition. Le produit par $z$ traduit un décalage d'un cran vers la droite de la suite originelle (on convient de ce que les termes de rang négatif sont nuls). Autrement dit :
   $$z\times S\left(n\mapsto u_{n}\right)\left(z\right)=S\left(n\mapsto u_{n-1}\right)\left(z\right)$$

6. Proposition. Décalage à gauche. On a :
   $$S\left(n\mapsto u_{n+1}\right)\left(z\right)=\frac{1}{z}\times \left(S\left(n\mapsto u_{n}\right)\left(z\right)-u_{0}\right)$$

7. Dérivation. La série génératrice de la suite $n\, u_{n}$ est donnée par :
   $$S\left(n\mapsto n\, u_{n}\right)\left(z\right)=z\times \frac{\mathrm{d}}{\mathrm{d}\, z}\left(S\left(n\mapsto u_{n}\right)\left(z\right)\right)$$

4.3 Exemples élémentaires

1. $S\left(n\right)\left(z\right)=\frac{z}{\left(1-z\right)^{2}}$. Méthode : on dérive $S\left(1\right)\left(z\right)=\frac{1}{1-z}$. Ne pas oublier de re-multiplier par $z$, car la dérivation décale les termes d'un cran vers la gauche.
2. $S\left(n+1\right)\left(z\right)=\frac{1}{\left(1-z\right)^{2}}$. Méthode : on remarque que $\left(n\mapsto n+1\right)=\left(n\mapsto 1\right)\star \left(n\mapsto 1\right)$, puisque $n+1=\sum _{k=0}^{k=n}\left(1\times 1\right)$.
3. On peut passer de (1) à (2) par la règle de décalage.
4. $S\left(n\mapsto n\left(n-1\right)\right)=\frac{2z^{2}}{\left(1-z\right)^{3}}$. Méthode : on dérive deux fois $S\left(1\right)\left(z\right)$.
5. $S\left(n\mapsto \frac{1}{2}n\left(n+1\right)\right)=\frac{z}{\left(1-z\right)^{3}}$. Méthode : on remarque que $\sum _{k=0}^{k=n}\left(1\times k\right)=\frac{n\left(n+1\right)}{2}$ et l'on procède par convolution. exo 79.  Calculer de différentes façons $S\left(n^{2}\right)\left(z\right)$.
   exo 80.  De même, calculer $S\left(n\mapsto n^{3}\right)\left(z\right)$ et $S\left(n\mapsto n^{4}\right)\left(z\right)$.

4.4 Les polynômes de Chebyschev

1. Proposition. $\cos \left(n\, t\right)$ s'exprime polynomialement à partir de $\cos t$.
2. Proposition. $\sin \left(n\, t\right)\div \sin t$ s'exprime polynomialement à partir de $\cos t$.
3. Définition. On appelle polynômes de Chebyschev (de première espèce) les polynômes $T_{n}\left(X\right)\in \mathbb{C}\left[X\right]$ tels que $\cos \left(n\, t\right)=T_{n}\left(\cos t\right)$.
   exo 81.  Déterminer les polynômes $T_{0}$ à $T_{5}$.
   exo 82.  Démontrer les deux propositions ci-dessus en partant de la formule $\exp \left(i\, t\right)=\cos t+i\, \sin t$.
4. Définition. On appelle polynômes de Gegenbauer les polynômes $U_{n}\left(X\right)\in \mathbb{C}\left[X\right]$ tels que $\sin \left(\left(n+1\right)\, t\right)=\sin t\times U_{n}\left(\cos t\right)$.
   exo 83.  Déterminer les polynômes $U_{0}$ à $U_{5}$.
   exo 84.  Montrer que les polynômes $T_{n}$ et $U_{n}$ sont de degré $n$ (attention aux décalages : $U_{2}$ est de degré $2$, mais concerne $\sin 3t$ !).
5. Une formule de trigo. On a $\cos p+\cos q=2\cos \frac{p+q}{2}\cos \frac{p-q}{2}$ .
   exo 85.  Retrouver ce résultat à partir de la formule de Moivre.
6. Formule de récurrence. On a donc $T_{n-1}\left(\cos t\right)+T_{n+1}\left(\cos t\right)=2\cos t\, T_{n}\left(\cos t\right)$, et par prolongement des identités :
   $$T_{n+1}\left(X\right)+T_{n-1}\left(X\right)=2X\, T_{n}\left(X\right)$$

7. Série génératrice. On multiplie par $z^{n}$ et on somme pour $1\leq n$. Il vient $\sum _{1}z^{n}\, T_{n+1}+\sum _{1}z^{n}\, T_{n-1}-2X\sum _{1}z^{n}T_{n}=0$, soit $\frac{1}{z}\sum _{2}z^{n}\, T_{n}+z\sum _{0}z^{n}\, T_{n}-2X\, \sum _{1}z^{n}\, T_{n}=0$ En posant $\sum _{0}z^{n}\, T_{n}=S\left(z\right)$, on obtient $S\left(z\right)\times \left(\frac{1}{z}+z-2X\right)=\frac{1}{z}\left(T_{0}+z\, T_{1}\right)-2X\, T_{0}=\frac{1}{z}-X$. Finalement :
   $$S\left(T_{n}\right)\left(z\right)\doteq \sum _{n\in \mathbb{N}}z^{n}\, T_{n}\left(X\right)=\frac{1-z\, X}{1-2z\, X+z^{2}}$$
   exo 86.  Déterminer de même la série génératrice des $U_{n}$. On constatera qu'il s'agit de la même récurrence, avec des conditions initiales différentes.

4.5 Séries génératrices et stats-probas

Reprise du cours de statistiques et probabilités du premier semestre.

1. Définition : série génératrice associée à une variable discrète $X$. Pour $z\in \mathbb{C}$, on pose :
   $S\left(z\right)=\sum _{k}Pr\left(X=k\right)\, z^{k}$ Une telle série converge uniformément pour $\left\vert z\right\vert\leq 1-\varepsilon$.

   exo 87.  Vérifier que, pour la loi de Bernoulli, $S\left(z\right)=q+p\, z$.

2. Résultats. Pour une variable discrète, on a
   $S\left(1\right)=\sum _{k}Pr\left(X=k\right)=1$,
   $S'\left(1\right)=\sum _{k}k\, Pr\left(X=k\right)=\mathrm{E}\left(X\right)$ et
   $S''\left(1\right)=\sum _{k}k\left(k-1\right)Pr\left(X=k\right)=\mathrm{E}\left(X\left(X-1\right)\right)$. On a donc :
   
   $$\mathrm{E}\left(X\right)=S'\left(1\right)\quad et\quad \mathrm{va... ...t(X\right)=S''\left(1\right)+S'\left(1\right)-\left(S'\left(1\right)\right)^{2}$$

   exo 88.  Vérifier ces formules pour la loi de Bernoulli.

3. Rappel (TAF). Si la fonction $f$ est dérivable sur $\left]a,\, b\right[$ et de plus est continue aux bornes, il existe $c\in \left]a,\, b\right[$ tel que $f\left(b\right)=f\left(a\right)+\left(b-a\right)f'\left(c\right)$. Bien entendu, on suppose $a\neq b$...
4. Rappel (L'Hôpital). Si les fonctions $f$ et $g$ sont dérivables sur $\left]a,\, b\right[$, continues aux bornes et si de plus $g'$ ne s'annule jamais, il existe $c\in \left]a,\, b\right[$ tel que $\frac{f\left(b\right)-f\left(a\right)}{g\left(b\right)-g\left(a\right)}=\frac{f'\left(c\right)}{g'\left(c\right)}$. Bien entendu, on suppose $a\neq b$...

   exo 89.  Vérifier que la série génératrice d'une variable uniforme sur $\left\{ 1,\, 2,\, \cdots ,\, m\right\}$ est $S\left(z\right)=\frac{z^{m+1}-z}{z-1}$. Combiner ce résultat avec la règle de L'Hôpital pour retrouver les paramètres de dispersion.

5. Théorème. La série génératrice de la somme de deux variables aléatoires discrètes INDÉPENDANTES est le produit des séries génératrices.
6. Rappel : loi binomiale. Une variable binomiale $K$ décrit le nombre de succès en $n$ épreuves de Bernoulli indépendantes, la probabilité de chaque succès individuel étant $p$.
   Formules : $Pr\left(K=k\right)={{n \choose k}}p^{k}q^{n-k}$ et $\mathrm{E}\left(K\right)=n\, p$, $\mathrm{var}\left(K\right)=n\, p\, q$.

   exo 90.  Vérifier que $S\left(z\right)=\left(q+p\, z\right)^{n}$. Utilisation pour retrouver $\mathrm{E}\left(K\right)$ et $\mathrm{var}\left(K\right)$.

7. Rappel : loi hypergéométrique. Définition : on prélève, sans remise et avec une probabilité uniforme, un échantillon de taille $n$ au sein d'une population de $N$ individus. On s'intéresse à un certain caractère binaire (i.e. présent ou absent), et on appelle $m$ le nombre d'occurences de ce caractère dans l'échantillon et $p$ sa prévalence (fréquence) dans la population. La loi hypergéométrique $Hyp\left(N,\, n,\, p\right)$ est $Pr\left(M=m\right)={{N\, p \choose m}}\times {{N\, q \choose n-m}}\div {{N \choose n}}$
   Formules : $\mathrm{E}\left(X\right)=np$ et $\mathrm{var}\left(X\right)=n\, p\, q\, \frac{N-n}{N-1}$.

   exo 91.  Déterminer la série génératrice associée. Commencer par des exemples.

8. Rappel : loi de Poisson. Il s'agit de la loi limite d'une loi binomiale pour laquelle $n\, p\rightarrow \lambda$ (ni nul ni infini) tandis que $n\rightarrow \infty$.
   Formules : $Pr\left(K=k\right)=\frac{\lambda ^{k}}{k!}\exp \left(-\lambda \right)$, $\mathrm{E}\left(K\right)=\lambda$ et $\mathrm{var}\left(K\right)=\lambda$.
   exo 92.  Vérifier que la série génératrice associée est $\exp \lambda \left(z-1\right)$. Utiliser cette série pour retrouver les paramètres de dispersion.