DevL'identité $\sum_{k=0}^n \binom{n}{k} = 2^n$ est l'une des plus célèbres en combinatoire. Elle admet deux démonstrations classiques qui éclairent chacune un aspect différent.
Démonstration combinatoire
Soit $E$ un ensemble à $n$ éléments. On compte le nombre total de sous-ensembles de $E$ de deux façons différentes.
D'une part, $\binom{n}{k}$ est le nombre de sous-ensembles à $k$ éléments. La somme $\sum_{k=0}^n \binom{n}{k}$ donne donc le nombre total de sous-ensembles (toutes tailles).
D'autre part, pour chaque élément de $E$ on a deux choix indépendants : l'inclure ou non dans le sous-ensemble. Cela donne $2^n$ sous-ensembles possibles.
Les deux comptages coïncident : $\sum_{k=0}^n \binom{n}{k} = 2^n$. ∎
Démonstration algébrique
On applique la formule du binôme de Newton à $(1+1)^n$ :
$$(1+1)^n = \sum_{k=0}^n \binom{n}{k} \cdot 1^{n-k} \cdot 1^k = \sum_{k=0}^n \binom{n}{k}$$
Mais $(1+1)^n = 2^n$. On obtient donc directement l'identité. ∎
Variantes utiles
En appliquant le binôme à $(1-1)^n$, on obtient l'identité alternée : $$\sum_{k=0}^n (-1)^k \binom{n}{k} = 0$$ (pour $n \ge 1$).
En dérivant le binôme $(1+x)^n$ et en évaluant en $x=1$, on obtient : $$\sum_{k=0}^n k \binom{n}{k} = n \cdot 2^{n-1}$$
À retenir
La méthode consistant à dériver ou intégrer la formule du binôme en $x$ permet d'obtenir de nombreuses identités combinatoires par voie algébrique.
Le triangle de Pascal et les sommes
La somme $\sum_{k=0}^n \binom{n}{k} = 2^n$ se lit directement sur le triangle de Pascal : chaque ligne $n$ somme à $2^n$. Ligne 0 : 1 = $2^0$. Ligne 4 : 1+4+6+4+1 = 16 = $2^4$.
On peut aussi démontrer cette identité par récurrence. $P(n) : \sum_{k=0}^n \binom{n}{k} = 2^n$.
Initialisation : $P(0)$ donne $\binom{0}{0} = 1 = 2^0$. ✓ Hérédité : supposons $P(n)$ et calculons $\sum_{k=0}^{n+1} \binom{n+1}{k}$. En utilisant Pascal $\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}$ et en réarrangeant, on obtient $2 \sum_{k=0}^n \binom{n}{k} = 2 \cdot 2^n = 2^{n+1}$.
Identité de Vandermonde
Une identité très utile, généralisation de la somme totale :
$$\sum_{k=0}^r \binom{m}{k} \binom{n}{r-k} = \binom{m+n}{r}$$
Démonstration combinatoire : le membre de droite compte les façons de choisir $r$ éléments parmi $m+n$. Le membre de gauche le fait par cas : choisir $k$ éléments parmi les $m$ premiers et $r-k$ parmi les $n$ autres.
En prenant $m = n = r$, on obtient le corollaire : $\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}$.
Une question ou une suggestion ? Écrivez-nous.