La formule de la crosse de hockey

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

Énoncé

Pour $0 \leq p \leq n$ , démontrer la formule « de la crosse de hockey » $k = p \sum n (p k) = (p + 1 n + 1),$ de deux façons : en classant les parties à $p + 1$ éléments de ${0, 1, \dots, n}$ selon leur plus grand élément, puis en télescopant la formule de Pascal. Application : calculer $\sum_{k = 1}^{n} k (k - 1)$ à l'aide de $\sum_{k = 2}^{n} (2 k)$ , et en déduire $\sum_{k = 1}^{n} k^{2}$ .

Corrigé

La stratégie. Deux voies : un double comptage, qui explique pourquoi la formule est vraie, et un télescopage de la formule de Pascal, qui la vérifie mécaniquement.

Première démonstration : le plus grand élément. Comptons les parties à $p + 1$ éléments de ${0, 1, \dots, n}$ , ensemble à $n + 1$ éléments. Directement : $(p + 1 n + 1)$ . Selon le plus grand élément : toute partie non vide a un plus grand élément $k$ , et un seul ; comme ses $p$ autres éléments sont strictement inférieurs à $k$ , on a $k \geq p$ . Se donner une partie de plus grand élément $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, pour $k$ de $p$ à $n$ , sont disjointes — une partie n'a qu'un maximum — et recouvrent tout : le principe d'addition donne la formule.

Seconde démonstration : Pascal télescopé. La formule de Pascal, $(p + 1 k + 1) = (p k) + (p + 1 k)$ , valable pour tout entier $k$ grâce à la convention, se relit $(p k) = (p + 1 k + 1) - (p + 1 k)$ : chaque terme est la différence de deux termes consécutifs de la suite $k \mapsto (p + 1 k)$ . En sommant de $k = p$ à $n$ , tout se télescope : $k = p \sum n (p k) = (p + 1 n + 1) - (p + 1 p) = (p + 1 n + 1) .$ Le point délicat est ce terme de bord : $(p + 1 p) = 0$ , car on ne choisit pas $p + 1$ éléments parmi $p$ . C'est cette convention qui referme proprement le télescopage.

Le nom. Dans le triangle de Pascal, les termes sommés forment un segment le long d'une diagonale, et le résultat est juste à côté de son extrémité, décalé d'un cran : le manche et la palette d'une crosse de hockey. Contrôle pour $p = 2$ , $n = 5$ : $1 + 3 + 6 + 10 = 20 = (3 6)$ .

L'application. Avec $p = 2$ : $\sum_{k = 2}^{n} (2 k) = (3 n + 1)$ , c'est-à-dire $\sum_{k = 1}^{n} \frac{k ( k - 1 )}{2} = \frac{( n + 1 ) n ( n - 1 )}{6}$ , le terme $k = 1$ étant nul ; donc $\sum_{k = 1}^{n} k (k - 1) = \frac{( n + 1 ) n ( n - 1 )}{3}$ . Comme $k^{2} = k (k - 1) + k$ et $\sum_{k = 1}^{n} k = (2 n + 1)$ , c'est-à-dire le cas $p = 1$ : $k = 1 \sum n k^{2} = \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} .$ Contrôle pour $n = 4$ : $1 + 4 + 9 + 16 = 30 = \frac{4 \times 5 \times 9}{6}$ .

Ce que l'exercice installe. Classer selon le plus grand élément : une partition indexée par le maximum transforme une somme en un seul coefficient binomial. Et la crosse de hockey est l'intégration discrète : la formule de Pascal joue le rôle d'une dérivation, le télescopage celui du théorème fondamental, et, comme $(p k)$ vaut à peu près $\frac{k ^{p}}{p !}$ pour $k$ grand, la formule est l'analogue discret de $\int_{0}^{x} \frac{t ^{p}}{p !} d t = \frac{x ^{p + 1}}{( p + 1 )!}$ .

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.