Exercice 21

Convergence. Pour $k \in \mathbb{N}$, la suite $\frac{n^{k+2}}{2^{n}}$ tend vers $0$ par croissances comparées (chapitre 7, théorème 7), donc $$\frac{n^{k}}{2^{n+1}} = \frac{1}{2} \cdot \frac{n^{k+2}}{2^{n}} \cdot \frac{1}{n^{2}} = o\Big(\frac{1}{n^{2}}\Big).$$ Le terme est positif, et la série $\sum \frac{1}{n^{2}}$ converge : la série $\sum \frac{n^{k}}{2^{n+1}}$ converge (théorème 3 (iii)).

Relation de récurrence. Soit $k \geqslant 1$. Le terme d'indice $0$ est nul, puisque $0^{k} = 0$, et l'on effectue le changement d'indice $n = m + 1$ sur les sommes partielles, avant de passer à la limite : $$\sum_{n=0}^{N+1} \frac{n^{k}}{2^{n+1}} = \sum_{m=0}^{N} \frac{(m + 1)^{k}}{2^{m+2}} = \frac{1}{2}\sum_{m=0}^{N} \sum_{j=0}^{k} \binom{k}{j}\frac{m^{j}}{2^{m+1}} = \frac{1}{2}\sum_{j=0}^{k} \binom{k}{j}\sum_{m=0}^{N} \frac{m^{j}}{2^{m+1}},$$ par la formule du binôme et l'interversion de deux sommes finies. Quand $N$ tend vers $+\infty$, chacune des $k + 1$ sommes intérieures tend vers $S_{j}$, et l'on obtient $S_{k} = \frac{1}{2}\sum_{j=0}^{k} \binom{k}{j}S_{j}$. Le terme $j = k$ vaut $\frac{1}{2}S_{k}$ ; on le fait passer à gauche : $$\boxed{S_{k} = \sum_{j=0}^{k-1} \binom{k}{j}S_{j} \quad\text{pour tout } k \geqslant 1}$$ Valeurs. On a $S_{0} = \sum_{n=0}^{+\infty} \frac{1}{2^{n+1}} = \frac{1}{2} \cdot \frac{1}{1 - \frac{1}{2}} = 1$ (théorème 1). Par récurrence forte, si $S_{0}$, …, $S_{k-1}$ sont entiers, $S_{k}$ l'est, comme somme de produits d'entiers : tous les $S_{k}$ sont des entiers naturels. La relation donne successivement $$S_{1} = S_{0} = 1, \qquad S_{2} = S_{0} + 2S_{1} = 3, \qquad S_{3} = S_{0} + 3S_{1} + 3S_{2} = 13,$$

$$\boxed{S_{0} = 1, \quad S_{1} = 1, \quad S_{2} = 3, \quad S_{3} = 13, \quad S_{4} = 75}$$ On contrôle $S_{1} = \sum_{n=0}^{+\infty} \frac{n}{2^{n+1}} = \frac{1}{4}\sum_{m=0}^{+\infty} (m + 1)\Big(\frac{1}{2}\Big)^{m}$ : la somme $\sum_{m=0}^{+\infty} (m + 1)z^{m} = \frac{1}{(1 - z)^{2}}$, obtenue dans le cours par un produit de Cauchy (section 20.7.4), vaut $4$ en $z = \frac{1}{2}$, et $S_{1} = \frac{1}{4} \times 4 = 1$ ✓. Les valeurs suivantes ont été vérifiées numériquement, ainsi que $S_{5} = 541$ et $S_{6} = 4683$.

À retenir. Ces entiers comptent les classements de $k$ concurrents lorsque les ex aequo sont permis : pour deux concurrents A et B, il y a les $3$ classements « A avant B », « B avant A » et « ex aequo ». En effet, si $F_{k}$ désigne ce nombre, avec $F_{0} = 1$, un classement de $k \geqslant 1$ concurrents est déterminé par le groupe non vide des premiers ex aequo, de cardinal $k - j$ avec $0 \leqslant j \leqslant k - 1$, à choisir de $\binom{k}{k - j} = \binom{k}{j}$ façons, puis par un classement des $j$ autres : $F_{k} = \sum_{j=0}^{k-1} \binom{k}{j}F_{j}$. C'est la relation de $S_{k}$, avec la même valeur initiale, donc $F_{k} = S_{k}$ pour tout $k$. Une somme de série qui compte des objets finis : c'est un premier exemple de ce que la seconde année appellera une série génératrice.