Formule du binôme de Newton (démonstration par dénombrement)

Dans cet article, nous allons démontrer la formule du binôme de Newton grâce à un raisonnement de dénombrement. 

On présuppose la connaissance des coefficients binomiaux. 

Tous les nombres sans précision supplémentaire seront réels, ou complexes (ou plus généralement des éléments d'un anneau commutatif).

Formule du binôme de Newton

Théorème. 

Soit $a,b$ deux nombres et $n$ un entier naturel. On a 

$$\left(a+b \right)^n=\binom n 0 a^n+\binom n 1 a^{n-1}b^1+\ldots+\binom n {1} a^{1}b^{n-1} + \binom n 0 b^n $$

Ou encore

$$\left(a+b \right)^n=\sum_{k=0}^{n} \binom n k a^{n-k}b^k$$

  

Remarque. Pour $n=0$, on a simplement, $(a+b)^0=1 $ car la somme ne comprend que le terme $\binom 0 0 a^{0}b^0=1$.

Démonstration. Parmi les différentes démonstrations possibles, je choisis une preuve par dénombrement. 

On écrit pour $n$ non-nul

$$(a+b)^n=\underbrace{(a+b)\times \ldots \times (a+b)}_{n \ \mathrm{facteurs}} $$

Lorsque l'on développe ce produit, on fait une somme de produit ayant $n$ facteurs, chaque facteur étant $a$ ou $b$. 

Par exemple, si $n=3$, on a 

$$(a+b)^3=(a+b)(a+b)(a+b)=aaa+aab+aba+abb+baa+bab+bba+bbb $$

On fait pour $n=3$, la somme des produits 

$$aaa,aab,aba,abb,baa,bab,bba,bbb $$

Pour former ces produits, on choisit un élément $a$ ou $b$ dans chaque $(a+b)$. $aab $ s'obtient en prenant $a$, puis $a$, puis $b$.

Ainsi on a $$(a+b)^3=a^3+a^2b+a^2b+ab^2+a^2b+ab^2+ab^2+b^3 $$

car on peut commuter les éléments dans chaque produit.  

On peut regrouper les $a^2b$ et les $ab^2$ pour obtenir 

$$(a+b)^3=a^3+3a^2b+3ab^2+b^3 $$

ce qui correspond bien à 

$$(a+b)^3=\binom 3 0 a^3+\binom 3 1 a^2b+\binom 3 2 ab^2+ \binom 3 3 b^3  $$

Attaquons-nous maintenant au cas général :

$$(a+b)^n=\underbrace{(a+b)\times \ldots \times (a+b)}_{n \ \mathrm{facteurs}} $$

En développant cette expression, on forme des produits de la forme $x_1x_2x_3\ldots x_n$, où chaque $x_i$ est un $a$ ou un $b$ provenant du $i-$ème facteur $(a+b)$. Comme le produit est commutatif, chaque terme $x_1x_2x_3\ldots x_n$ est ainsi de la forme $a^kb^m $ où $k+m=n$. Autrement dit, on obtient une somme de terme de la forme $a^kb^{n-k} $, avec $0\leq k\leq n$. 

Former un terme de la forme $a^kb^{n-k}$ revient à former choisir $k$ facteurs $(a+b)$ où l'on prend le $a$, et pour les autres facteurs $(a+b)$, on prend automatiquement $b$. Ainsi il y a autant de termes $a^kb^{n-k}$ qu'il y a de façons de choisir $k$ éléments parmi $n$ : c'est le nombre de sous-ensembles de $k$ éléments parmi $n$, soit le coefficient binomial $\binom n k$. 

On a donc prouvé que

$$\left(a+b \right)^n=\sum_{k=0}^{n} \binom n k a^{n-k}b^k$$

Nombre de parties d'un ensemble

Exemple 1.

Cela permet de montrer l'identité

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

En effet, il suffit de prendre $a=b=1$ dans la formule du binome de Newton.

Remarquons  que cette identité $(1)$ se retrouve par un raisonnement de dénombrement.
En effet considérons un ensemble $E$ constitué de $n$ éléments. On note $\mathcal P(E)$ l'ensemble des parties de $E$, c'est-à-dire l'ensemble dont les éléments sont les sous-ensembles de $E$.
Nous allons le montrer ci-après

Nombres de parties d'un ensemble fini

On a par définition

$$\mathcal P(E)=\left\{F| \ F\subset E \right\} $$

On peut organiser les sous-ensembles de $E$ en $n+1$ classes en fonction de leur nombre d'éléments :   

$$\mathcal P(E)=\mathcal P_0 \cup \mathcal P_1 \cup \ldots \cup \mathcal P_n$$ 

où chaque $\mathcal P_i$ désigne l'ensemble des sous-ensemble de $E$ ayant $i$ éléments. Par définition de $\binom n i$, $\mathcal P_i$ possède $\binom n i$ éléments. 

Comme les $\mathcal P_i $ sont disjoints, la somme de leurs cardinaux est donc au cardinal de $\mathcal P $.

Autrement dit, le nombre de sous-ensembles de $E$ est donc égal à $\sum_{k=0}^{n} \binom n k$.

Il nous reste à montrer que le nombre de sous-ensemble de $E$ est $2^n$.

Soit $F$ un sous-ensemble de $E$, pour former $F$, cela revient pour tout élément de $E$ à sélectionner ou non cet élément. Ainsi pour chaque élément, on a 2 possibilité : être choisi ou ne pas être choisi. Cela donne donc

$$\underbrace{2\times \ldots \times 2}_{n\ \mathrm{facteurs}} $$

façons de constituer $F$. 

Il y a donc bien $2^n$ sous-ensembles distincts de $E$. 

Ceci montre notre affirmation.

Remarque. Cela revient à déterminer le nombre de fonctions de l'ensemble $$E_n=\left\{1,2,\ldots,n \right\} $$

vers l'ensemble $\left\{0,1\right\}$.

Et ensuite

Dans un prochain article, on pourra s'intéresser à diverses application de la formule du binôme de Newton.