Algèbre et géométrie · Tle
Démonstration : la somme des coefficients binomiaux
Compter deux fois le même ensemble, de deux façons différentes, et poser que les deux résultats sont forcément égaux : c'est tout le principe d'une preuve par dénombrement.
La démonstration en vidéo
Le vocabulaire à connaître
- double comptage
- Une méthode de preuve : compter un même ensemble de deux façons différentes prouve que les deux résultats obtenus sont égaux.
Ce qu'on sait
- Le nombre de parties d'un ensemble à n éléments est 2ⁿ (chaque élément est, ou n'est pas, dans la partie : 2 choix indépendants par élément).
- Le nombre de parties à k éléments d'un ensemble à n éléments est, par définition, (ⁿₖ).
- Toute partie d'un ensemble à n éléments a un nombre d'éléments bien déterminé, compris entre 0 et n.
La méthode, étape par étape
1.Je considère un ensemble E à n éléments, et je compte le nombre de parties de E de deux façons différentes.
2.Première façon : je décide, pour CHACUN des n éléments, s'il fait partie de la partie construite ou non — 2 choix indépendants par élément, donc 2ⁿ parties en tout, par le principe multiplicatif.
3.Deuxième façon : je classe les parties de E selon leur nombre d'éléments k, avec k allant de 0 à n. Le nombre de parties à k éléments est, par définition, (ⁿₖ).
4.Chaque partie de E a un nombre d'éléments bien déterminé : je retrouve donc le nombre total de parties en additionnant, pour k allant de 0 à n, le nombre de parties à k éléments : Σₖ₌₀ⁿ (ⁿₖ).
5.Les deux comptages dénombrent le même ensemble (les parties de E) : ils sont donc égaux, ce qui donne Σₖ₌₀ⁿ (ⁿₖ) = 2ⁿ.
Pour tout entier naturel n, Σₖ₌₀ⁿ (ⁿₖ) = 2ⁿ.
C.Q.F.D.
L'exemple au propre
1.Prenons n = 3, avec l'ensemble E formé des trois éléments 1, 2 et 3.
2.(³₀) = 1 (l'ensemble vide), (³₁) = 3, (³₂) = 3, (³₃) = 1 (E lui-même).
3.1 + 3 + 3 + 1 = 8.
4.Et 2³ = 8 : les deux comptages coïncident, comme prévu.