Formule du binôme de Newton

Démonstration :

Par récurrence sur l'entier $n$.

1. Initialisation : Lorsque $n=0$, les deux membres sont égaux à 1 (avec le cas échéant la convention $0^0=1$).
2. Récurrence : Supposons la formule vraie au rang $n$, et montrons qu'elle est encore vraie au rang $n+1$ :

\[ \begin{eqnarray*} (a+b)^{n+1} & = & (a+b)(a+b)^n \stackrel{\text{Réc.}}{=} (a+b) \sum_{k=0}^n C_n^k \, a^k\, b^{n-k} \\ & = & \sum_{k=0}^nC_n^k\, a^{k+1}\, b^{n-k} + \sum_{k=0}^n C_n^k\, a^k\, b^{n-k+1} \\ & = & \sum_{k=1}^{n+1} C_n^{k-1} \, a^k\, b^{n-k+1} + \sum_{k=0}^n C_n^k\, a^k\, b^{n-k+1} \\ & = & \underbrace{a^{n+1}}_{(k=n+1)}+\sum_{k=1}^{n} C_n^{k-1} \, a^k\, b^{n-k+1}+\underbrace{b^{n+1}}_{(k=0)}+\sum_{k=1}^n C_n^k\, a^k\, b^{n-k+1} \\ & = & C_{n+1}^0\,a^0\,b^{n+1} + \sum_{k=1}^{n} \left(C_n^{k-1} + C_n^k \right)\,a^k\,b^{n+1-k} + C_{n+1}^{n+1} \,a^{n+1}\,b^0 \\ & = & \sum_{k=0}^{n+1} C_{n+1}^k \,a^k\,b^{n-k}. \end{eqnarray*} \]

La dernière égalité utilise la formule de Pascal pour l'addition des deux coefficients binomiaux.

On a les égalités suivantes : \[ \text{(i)} \sum_{k=0}^n C_n^k = 2^n \qquad ; \qquad \text{(ii)} \sum_{k=0}^n (-1)^k\,C_n^k = 0. \]

Pour (i), on utilise le théorème précédent avec $a=1$ et $b=1$. Pour (ii), on l'utilise avec $a=-1$ et $b=1$.

Le point (i) traduit le fait que le nombre de parties d'un ensemble à $n$ éléments est $2^n$. En effet, ce nombre est la somme des nombres de parties ayant respectivement 0, 1, … éléments (le cardinal d'une union disjointe est la somme des cardinaux), ce qui correspond bien à la somme indiquée.