Démonstration de ∑ k·C(n,k) = n·2^(n-1)

L'identité $\sum_{k=0}^n k \binom{n}{k} = n \cdot 2^{n-1}$ apparaît fréquemment en combinatoire et en probabilités. Deux démonstrations classiques permettent de la comprendre.

Démonstration combinatoire

On compte de deux façons le nombre de couples $(A, a)$ où $A$ est un sous-ensemble d'un ensemble $E$ à $n$ éléments, et $a \in A$ un élément distingué.

D'une part : pour $A$ à $k$ éléments, il y a $\binom{n}{k}$ choix pour $A$ et $k$ choix pour $a$. En sommant sur $k$ : $\sum_{k=0}^n k \binom{n}{k}$.

D'autre part : on choisit d'abord $a$ ($n$ possibilités), puis un sous-ensemble parmi les $n-1$ autres éléments (il y a $2^{n-1}$ tels sous-ensembles, $a$ étant déjà fixé). Soit $n \cdot 2^{n-1}$.

Les deux comptages sont égaux. ∎

Démonstration algébrique

Partons du binôme de Newton : $(1+x)^n = \sum_{k=0}^n \binom{n}{k} x^k$.

On dérive les deux membres par rapport à $x$ : $n(1+x)^{n-1} = \sum_{k=0}^n k \binom{n}{k} x^{k-1}$.

On évalue en $x = 1$ : $n \cdot 2^{n-1} = \sum_{k=0}^n k \binom{n}{k}$. ∎

Généralisation : ∑ k² C(n,k)

La technique de double dérivation permet d'obtenir des sommes d'ordre supérieur. Partant de $\sum k \binom{n}{k} x^k = nx(1+x)^{n-1}$ (obtenue par dérivation puis multiplication par $x$), on dérive à nouveau et on évalue en $x=1$ :

$$\sum_{k=0}^n k^2 \binom{n}{k} = n(n+1) \cdot 2^{n-2}$$

Vérification pour $n=3$ : $0 + 1 \cdot 3 + 4 \cdot 3 + 9 \cdot 1 = 24$ et $3 \cdot 4 \cdot 2 = 24$. ✓

Interprétation probabiliste

Pour $X \sim \mathcal{B}(n, 1/2)$, on a $E[X] = n/2$. L'espérance est $E[X] = \sum k \cdot P(X=k) = \sum k \cdot \binom{n}{k} / 2^n$.

De là : $\sum k \binom{n}{k} = 2^n \cdot n/2 = n \cdot 2^{n-1}$. C'est notre identité, redémontrée via probabilités.

Cette connexion entre combinatoire et probabilités est l'une des plus fertiles : chaque identité combinatoire admet en général une lecture probabiliste.

Une question ou une suggestion ? Écrivez-nous.