Dans cet article, nous allons démontrer et corriger la formule de Vandermonde, une formule appelant une somme qui peut s’avérer utile.
Enoncé de la formule de Vandermonde
Soient a, b et n trois entiers tels que n \leq a+b. La formule de Vandermonde s’écrit
\binom{a+b}{n} = \sum_{k=0}^n \binom{a}{k}\binom{b}{n-k}
Démonstration de la formule de Vandermonde
Démonstration 1 : Par le calcul
Nous allons commencer par une démonstration calculatoire : on considère le polynôme P défini par P(X) = (1+X)^{a+b} = (1+X)^a (1+X)^b.
D’une part :
(1+X)^{a+b} = \sum_{k=0}^{a+b} \binom{a+b}{k} X^k
D’autre part :
\begin{array}{ll} (1+X)^a (1+X)^b & =\displaystyle \sum_{i=0}^{a} \binom{a}{i} X^i \sum_{j=0}^{b} \binom{b}{j} X^j\\ & =\displaystyle \sum_{k=0}^{a+b}\sum_{i+j=k} \binom{a}{i} X^i \binom{b}{j} X^j\\ & =\displaystyle \sum_{k=0}^{a+b}\sum_{i+j=k} \binom{a}{i}\binom{b}{j} X^{i+j}\\ & =\displaystyle \sum_{k=0}^{a+b} \left(\sum_{i=0}^k \binom{a}{i}\binom{b}{k-i}\right)X^{k} \end{array}
En prenant le terme de degré n de chaque côté, on obtient :
\binom{a+b}{n} = \sum_{i=0}^n \binom{a}{i}\binom{b}{n-i}
Ce qui est bien la formule recherchée
Démonstration 2 : Par dénombrement
Considérons un ensemble E de cardinal a+b. Pour cet ensemble, on a \binom{a+b}{n} façons de choisir un sous-ensemble à n éléments.
D’autre part, si on découpe cet ensemble en deux ensembles de a et b éléments :
- On choisit k éléments dans le premier ensemble : on a \binom{a}{k} façons de les choisir
- Il reste donc n – k éléments à choisir dans le second ensemble, on a \binom{b}{n-k} façons de les choisir
- On fait varier k de 0 à n : \displaystyle \sum_{k=0}^n \binom{a}{k} \binom{b}{n-k}
On a dénombré le même ensemble de deux manières différentes :
\binom{a+b}{n}=\sum_{k=0}^n \binom{a}{k} \binom{b}{n-k}
Le corrigé en vidéo
Pour ceux qui préfèrent, voici le corrigé de la formule de Vandermonde en vidéo :