Analyse combinatoire et dénombrement

Le binôme de Newton :

Nous allons voir maintenant une formule qui sera par la suite utilisée très souvent en mathématiques, la formule du binôme de Newton, mais avant, revenons sur une identité remarquable que vous devriez bien connaître :

(a+b)^2

Quel est le rapport nous direz vous ?
En fait, en regardant le triangle de Pascal plus attentivement, on remarque quelque chose… Il faut évidemment être attentif et inventif… Nous allons vous mettre sur la voie…

Vous ne voyez pas ?

Que vaut (a+b)^2 ? (a+b)^2=a^2+2ab+b^2=1a^2+2ab+1b^2.

Peut on calculer (a+b)^3 ? On ne pas connait l’identité remarquable pour cet indice (l’identité est connue, on suppose simplement ici qu’on ne la connait pas). On peut facilement calculer la valeur pour cet indice en développant :

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

Remarquez-vous quelque chose ? Regardez à nouveau le triangle de Pascal…
Chaque ligne du triangle de Pascal définie les coefficients de l’identité remarquable (a+b)^2 en la généralisant à (a+b)^n, avec n \in \mathbb{N}

On voit bien que pour n’importe quel n, il suffit de regarder le triangle de Pascal pour connaître les coefficients… Mais… C’est certes remarquable, et très pratique, cependant, pour des grandes puissances de n, ça ne nous aide pas, et nous oblige nécessairement à effectuer des calculs laborieux… Il faut donc trouver un moyen de construire une formule qui nous permettrait d’expliciter rapidement le résultat…

Observons le comportement des indices dans les formules pour n=2 et n=3, que voit-on ?

  • On remarque que les puissances de a vont en décroissant de la gauche vers la droite et les puissances de b vont en décroissant de la droite vers la gauche.
  • On remarque que chaque terme est le produit d’une puissance de a et d’une puissance de b
  • On voit que la somme des indices (puissances) de a et b dans chaque terme est égal à n.

Donc, on pourrait construire une somme de coefficients, ou l’indice général de a serait n-k par exemple, pourquoi ?
On sait que le premier terme inclus que k=0, et donc que n-k=n.
Chaque terme étant le produit d’une puissance de a et b, cela inclus qu’on multiplie par b^k. En effet, sur le premier, on a k=0 et on voit bien que b=1, étant donné que k=0, on a b^0=1

En fait, la conséquence de ce raisonnement est la formule du binôme de Newton, qui est la suivante :

\displaystyle{(a+b)^n=\sum_{k=0}^n \begin{pmatrix}n \\ k \end{pmatrix} a^{n-k} b^k} avec a,b \in \mathbb{R} et n,k \in \mathbb{N}

Ceci est évidemment égal à :

\displaystyle{(a+b)^n=\sum_{k=0}^n \begin{pmatrix}n \\ k \end{pmatrix} a^{k} b^{n-k}}

*Pour la simple raison que nous sommes dans \mathbb{R}, qui est un corps, et est donc commutatif.

On peut vérifier que la formule est la bonne, pour cela, il faut appliquer un raisonnement par récurrence. On vérifie que la formule est vraie pour n=0 (on peut le faire également pour n=1), et ensuite, on suppose qu’elle est vraie au rang n, et de ce fait, on arrive à montrer qu’elle est vraie au rang n+1.

On va donc commencer avec l’initialisation. On vérifie donc, que la formule est vrai au rang n=0 :

\displaystyle{(a+b)^n=\sum_{k=0}^0 \begin{pmatrix}0 \\ 0 \end{pmatrix} a^0 b^0=1}

La formule est donc vraie pour n=0, à présent, l’hérédité, dont la démonstration va être légèrement plus compliquée…

On pose donc :

(a+b)^{n+1}=(a+b)^n(a+b)

Maintenant, on développe grâce à la formule du binôme :

\displaystyle{(a+b)^{n+1}=\Big[\sum_{k=0}^n \begin{pmatrix}n \\ k \end{pmatrix} a^{k} b^{n-k}\Big] (a+b)}

Comment regrouper les termes ? On pourrait se dire, on multiplie simplement par a et b et se servant de la loi d’associativité, alors oui, on peut tout à faire cela :

\displaystyle{(a+b)^{n+1}=\sum_{k=0}^n \begin{pmatrix}n \\ k \end{pmatrix} a^{k+1} b^{n-k}+\sum_{k=0}^n \begin{pmatrix}n \\ k \end{pmatrix} a^{k} b^{n+1-k}}

Très bien, analysons un peu la situation. Nous, nous voulons arriver à cette formule :

\displaystyle{(a+b)^{n+1}=\sum_{k=0}^{n+1} \begin{pmatrix}n+1 \\ k \end{pmatrix} a^k b^{n+1-k}}

Seulement, quand on regarde notre formule, on a petit problème. En effet, on a d’un côté un a^{k+1} et de l’autre un a^k
Pas de problème, il nous suffit de changer l’indice de la somme… En revanche, si on rétrograde de 1 l’indice du coefficient, en changeant a^{k+1} en a^k, il faut nécessairement débuter la somme au k+1 ième terme et finir au n+1 ième, autrement dit, on a :

\displaystyle{(a+b)^{n+1}=\sum_{k=1}^{n+1} \begin{pmatrix}n \\ k-1 \end{pmatrix} a^k b^{n-(k-1)}+\sum_{k=0}^n \begin{pmatrix}n \\ k \end{pmatrix} a^{k} b^{n+1-k}}

Bon… nous nous sommes débarrassé d’un problème, mais nous en avons maintenant un autre… En effet, les deux sommes ne commencent et ne terminent pas au même rang…
Qu’à cela ne tienne, il y a quelque chose à faire, le voyez-vous ?

En fait, on voit bien que ces deux sommes ne sont pas compatibles et qu’on ne peut pas les réunir en une seule, mais… Nous allons « tricher », nous allons séparer des deux sommes, les termes dont nous n’avons pas « besoin ».
Pour la première somme, nous allons isoler le terme en k=n+1, et pour la deuxième, le terme en k=0, on a alors :

\displaystyle{(a+b)^{n+1}=\begin{pmatrix} n \\ n \end{pmatrix}a^{n+1}b^0+\begin{pmatrix} n \\ 0 \end{pmatrix}a^0b^{n+1}+\sum_{k=1}^{n} \begin{pmatrix}n \\ k-1 \end{pmatrix} a^k b^{n-(k-1)}+\sum_{k=1}^n \begin{pmatrix}n \\ k \end{pmatrix} a^{k} b^{n+1-k}}

*Pourquoi \displaystyle{\begin{pmatrix} n \\ n \end{pmatrix}} et pas \displaystyle{\begin{pmatrix} n+1 \\ n+1 \end{pmatrix}} sur le premier terme? Tout simplement car c’est la même chose, \displaystyle{\begin{pmatrix} n+1 \\ n+1 \end{pmatrix}= \begin{pmatrix} n \\ n \end{pmatrix}}
De même, \displaystyle{\begin{pmatrix} n+1 \\ 0 \end{pmatrix}= \begin{pmatrix} n \\ 0 \end{pmatrix}}.

A présent, remarquons autre chose… Il est possible maintenant que les sommes ont les mêmes indices, de les rassembler :

\displaystyle{(a+b)^{n+1}=\begin{pmatrix} n \\ n \end{pmatrix}a^{n+1}b^0+\begin{pmatrix} n \\ 0 \end{pmatrix}a^0b^{n+1}+\sum_{k=1}^{n} \Big[\begin{pmatrix}n \\ k-1 \end{pmatrix}+\begin{pmatrix}n \\ k \end{pmatrix}\Big] a^k b^{n+1-k}}

On peut encore simplifier, en effet, on sait que : \begin{pmatrix}n \\ k-1 \end{pmatrix}+\begin{pmatrix}n \\ k \end{pmatrix}=\begin{pmatrix}n+1 \\ k \end{pmatrix}

Donc :

\displaystyle{(a+b)^{n+1}=\begin{pmatrix} n \\ n \end{pmatrix}a^{n+1}b^0+\begin{pmatrix} n \\ 0 \end{pmatrix}a^0b^{n+1}+\sum_{k=1}^{n} \begin{pmatrix}n+1 \\ k \end{pmatrix} a^k b^{n+1-k}}

En fait, nous avons fini, car il suffit à présent de regrouper les termes en une même somme. En effet, on voit bien que le premier terme est le terme en k=n+1 et le deuxième est le terme en k=0, par conséquent :

\displaystyle{(a+b)^{n+1}=\sum_{k=0}^{n+1} \begin{pmatrix}n+1 \\ k \end{pmatrix} a^k b^{n+1-k}}

On tombe sur la formule qu’on voulait trouver, par conséquent, l’hérédité est démontrée, et la formule du binôme de Newton est vraie pour tout n \in \mathbb{N}.