La crosse de hockey

Exercice de TD · niveau 3 (difficile) · mathématiques MPSI, chapitre 18 — Dénombrement · C. Combinaisons et identités

Énoncé

Pour $0 \leq p \leq n$ , démontrer $k = p \sum n (p k) = (p + 1 n + 1)$ (les coefficients se lisent « $p$ parmi $k$ » et « $p + 1$ parmi $n + 1$ »), de deux façons : par la formule de Pascal, puis par un double comptage. En déduire $k = 1 \sum n k^{2} = \frac{n ( n + 1 ) ( 2 n + 1 )}{6}$ .

Corrigé

La stratégie. Deux voies : la première est un télescopage déguisé de la formule de Pascal ; la seconde compte un même ensemble de deux façons, et c'est elle qui explique pourquoi la formule est vraie.

Première démonstration — Pascal télescopé. La formule de Pascal, $(p + 1 k + 1) = (p k) + (p + 1 k)$ , se relit $(p k) = (p + 1 k + 1) - (p + 1 k) .$ Le terme général de la somme est donc un accroissement de la suite $b_{k} = (p + 1 k)$ , et la somme se télescope : $k = p \sum n (p k) = k = p \sum n (b_{k + 1} - b_{k}) = b_{n + 1} - b_{p} = (p + 1 n + 1) - (p + 1 p) = (p + 1 n + 1) .$ Le point délicat est ce terme de bord. $(p + 1 p) = 0$ par convention : on ne peut pas choisir $p + 1$ éléments dans un ensemble qui n'en a que $p$ . C'est cette convention, et elle seule, qui fait disparaître le reste. L'oublier laisserait un terme parasite.

Seconde démonstration — un double comptage. Comptons de deux façons les parties à $p + 1$ éléments de ${0, 1, \dots, n}$ , ensemble à $n + 1$ éléments. Directement : il y en a $(p + 1 n + 1)$ . Par leur plus grand élément : toute partie $P$ à $p + 1$ éléments, finie et non vide, possède un maximum $k$ ; comme $P$ a $p$ autres éléments, tous strictement inférieurs à $k$ , on a $k \geq p$ . Réciproquement, se donner $P$ de maximum $k$ , c'est se donner ses $p$ autres éléments dans ${0, \dots, k - 1}$ , qui a $k$ éléments : $(p k)$ choix. Les classes indexées par $k \in {p, \dots, n}$ sont deux à deux disjointes — une partie n'a qu'un maximum — et recouvrent tout. Par le principe d'addition, $(p + 1 n + 1) = k = p \sum n (p k) .$ Ce qui rend le découpage licite, ce sont exactement ces deux mots, disjointes et recouvrantes : un découpage qui oublie un cas ou en compte un deux fois ne prouve rien.

Le nom. Dans le triangle de Pascal, les termes de la somme forment un segment oblique, et le résultat est le nombre situé juste en dessous de son extrémité, décalé d'un cran : le manche, puis la palette d'une crosse de hockey. Contrôle : $p = 2$ , $n = 5$ : $1 + 3 + 6 + 10 = 20 = (3 6)$ .

L'application : la somme des carrés. Avec $p = 1$ : $k = 1 \sum n k = k = 1 \sum n (1 k) = (2 n + 1) = \frac{n ( n + 1 )}{2}$ . Avec $p = 2$ : $k = 2 \sum n (2 k) = (3 n + 1)$ , c'est-à-dire $k = 1 \sum n \frac{k ( k - 1 )}{2} = \frac{( n + 1 ) n ( n - 1 )}{6}$ , le terme $k = 1$ étant nul. Or $k^{2} = k (k - 1) + k$ , donc $k = 1 \sum n k^{2} = 2 (3 n + 1) + (2 n + 1) = \frac{( n + 1 ) n ( n - 1 )}{3} + \frac{n ( n + 1 )}{2} = \frac{n ( n + 1 ) ( 2 ( n - 1 ) + 3 )}{6} = \frac{n ( n + 1 ) ( 2 n + 1 )}{6} .$ Le même geste — écrire un polynôme en $k$ dans la base $(0 k), (1 k), (2 k), \dots$ — donne la somme de n'importe quel polynôme.

Ce que l'exercice installe. Classer selon le plus grand élément : une partition de l'ensemble compté, indexée par le maximum, qui transforme une somme en un unique coefficient binomial. Et la crosse de hockey est l'identité qui somme les polynômes ; c'est elle aussi qui, au chapitre 17, calcule le coefficient du produit de Cauchy de $\frac{1}{( 1 - z ) ^{2}}$ par $\frac{1}{1 - z}$ .

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.