Une identité, deux démonstrations

Exercice d'entraînement · niveau 2 · mathématiques appliquées (ECG 1re année), chapitre 6 — Probabilités et statistiques · Dénombrement et coefficients binomiaux

Énoncé

Montrer que pour $1 \leq k \leq n$ : $k (k n) = n (k - 1 n - 1)$ , d'abord par la formule explicite, puis par un double comptage. En déduire la valeur de $\sum_{k = 1}^{n} k (k n)$ .

Corrigé

Par la formule explicite. On part du membre de gauche, en utilisant $(k n) = \frac{n !}{k ! ( n - k )!}$ : $k (k n) = k \times \frac{n !}{k ! ( n - k )!} = \frac{n !}{( k - 1 )! ( n - k )!},$ la simplification $\frac{k}{k !} = \frac{1}{( k - 1 )!}$ étant licite car $k \geq 1$ . D'autre part, en écrivant $n! = n \times (n - 1)!$ et en remarquant que $n - k = (n - 1) - (k - 1)$ : $\frac{n !}{( k - 1 )! ( n - k )!} = n \times \frac{( n - 1 )!}{( k - 1 )! ( ( n - 1 ) - ( k - 1 ) ) !} = n (k - 1 n - 1) .$

Par double comptage. Comptons de deux façons les paires formées d'un comité de $k$ personnes choisies parmi $n$ et d'un président désigné dans ce comité.

En choisissant d'abord le comité : $(k n)$ comités possibles, puis $k$ choix pour le président. Total : $k (k n)$ .
En choisissant d'abord le président : $n$ possibilités, puis il reste à compléter le comité avec $k - 1$ personnes prises parmi les $n - 1$ restantes, soit $(k - 1 n - 1)$ façons. Total : $n (k - 1 n - 1)$ .

Les deux comptages portent sur le même ensemble : ils sont égaux.

La somme. En appliquant l'identité puis en changeant d'indice ( $j = k - 1$ ) : $k = 1 \sum n k (k n) = n k = 1 \sum n (k - 1 n - 1) = n j = 0 \sum n - 1 (j n - 1) = n 2^{n - 1},$ la dernière somme valant $2^{n - 1}$ puisqu'elle compte toutes les parties d'un ensemble à $n - 1$ éléments.

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.