Prouver des identités combinatoires
Énoncé
Démontrer les identités suivantes :
a) Σ(k=0→n) (-1)ᵏ C(n,k) = 0 pour n ≥ 1.
b) Σ(k=0→n) k C(n,k) = n · 2ⁿ⁻¹.
c) C(n,0)² + C(n,1)² + ⋯ + C(n,n)² = C(2n,n).
Indice : a) Utiliser le binôme avec a=1, b=-1. b) Utiliser la formule d'absorption kC(n,k) = nC(n-1,k-1). c) Utiliser l'identité de Vandermonde.
Correction
- Étape 1 : Trois identités à démontrer, et la même stratégie pour les trois : appliquer le binôme de Newton à un choix bien choisi de a, b ou x.
👉 C'est ce qu'il faut retenir de cet exercice : une identité sur les C(n,k) se démontre presque toujours en spécialisant le binôme, pas en manipulant des factorielles.
⚠️ Les questions b) et c) reposent sur deux résultats qui portent des noms savants — « formule d'absorption », « identité de Vandermonde ». Ces noms ne sont PAS au programme, et il n'y a aucune raison de les invoquer sans preuve : les deux se démontrent en trois lignes avec les outils du chapitre, et c'est ce qu'on fait ci-dessous.
- Étape 2 : a) On applique le binôme avec a = 1 et b = -1 :
(1 + (-1))ⁿ = Σ(k=0→n)C(n,k) 1ⁿ⁻ᵏ (-1)ᵏ = Σ(k=0→n)(-1)ᵏC(n,k)
(car 1ⁿ⁻ᵏ = 1 quel que soit l'exposant)
Or le membre de gauche vaut 0ⁿ = 0 pour n ≥ 1 :
Σ(k=0→n)(-1)ᵏC(n,k) = 0
⚠️ La condition n ≥ 1 n'est pas une précaution rhétorique : pour n = 0, la somme se réduit à C(0,0) = 1, et 0⁰ = 1 par convention. L'identité serait donc 1 = 1 — vraie, mais pas « égale à 0 ».
ℹ️ Contrôle sur n = 4 : 1 - 4 + 6 - 4 + 1 = 0 ✓ — les coefficients du triangle de Pascal, pris alternativement, se compensent exactement.
Σ(k=0→n)(-1)ᵏC(n,k) = 0 (n ≥ 1)
- Étape 3 : b) On commence par démontrer la formule dite « d'absorption », qui n'a rien de mystérieux :
kC(n,k) = k × (n!)/(k! (n-k)!) = (n!)/((k-1)! (n-k)!)
(le k simplifie un facteur de k! = k × (k-1)!)
On fait maintenant apparaître n en facteur, en écrivant n! = n × (n-1)! :
= n × ((n-1)!)/((k-1)! (n-k)!) = nC(n-1,k-1)
(car (n-1) - (k-1) = n-k, l'exposant du dénominateur est bien le bon)
kC(n,k) = nC(n-1,k-1)
👉 Trois lignes de calcul sur des factorielles — rien d'autre. Il n'y avait aucune raison de citer un nom.
kC(n,k) = nC(n-1,k-1)
- Étape 4 : On l'applique à la somme. Le terme k=0 est nul (il vaut 0 × C(n,0)), on peut donc démarrer à k=1 :
Σ(k=0→n)kC(n,k) = Σ(k=1→n)nC(n-1,k-1) = nΣ(k=1→n)C(n-1,k-1)
On change d'indice en posant j = k-1 : quand k va de 1 à n, j va de 0 à n-1.
= nΣ(j=0→n-1)C(n-1,j)
Et cette somme vaut 2ⁿ⁻¹ (c'est l'identité Σₖ C(m,k) = 2ᵐ avec m = n-1) :
Σ(k=0→n)kC(n,k) = n · 2ⁿ⁻¹
ℹ️ Contrôle sur n = 5 : 0 + 5 + 2(10) + 3(10) + 4(5) + 5(1) = 5+20+30+20+5 = 80, et 5 × 2⁴ = 80 ✓
Σ(k=0→n)kC(n,k) = n 2ⁿ⁻¹
- Étape 5 : c) Le principe : une même quantité comptée de deux façons.
On part de l'égalité évidente (1+x)ⁿ × (1+x)ⁿ = (1+x)²ⁿ, et l'on compare le coefficient de xⁿ des deux côtés.
À droite, par le binôme appliqué à (1+x)²ⁿ : le coefficient de xⁿ est C(2n,n).
À gauche, on développe chaque facteur. Un terme en xⁿ s'obtient en prenant xᵏ dans le premier facteur et xⁿ⁻ᵏ dans le second, pour un k allant de 0 à n. Le coefficient total est donc la somme de tous ces produits :
Σ(k=0→n)C(n,k)C(n,n-k)
Et par symétrie C(n,n-k) = C(n,k) :
= Σ(k=0→n)C(n,k)²
Les deux expressions comptant la même chose :
Σ(k=0→n)C(n,k)² = C(2n,n)
ℹ️ Contrôle sur n=4 : 1²+4²+6²+4²+1² = 1+16+36+16+1 = 70, et C(8,4) = 70 ✓
Σ(k=0→n)C(n,k)² = C(2n,n)
- Étape 6 : L'erreur classique :
Invoquer un résultat par son nom — « d'après Vandermonde » — sans savoir le démontrer.
En devoir, cela ne vaut aucun point : un nom n'est pas une preuve, et ces résultats ne sont pas au programme. Or les trois démonstrations ci-dessus n'emploient que le binôme, la symétrie et une simplification de factorielles — tout est disponible.
👉 Un nom savant est un signal, pas un obstacle : il indique qu'un résultat est connu, donc probablement démontrable avec ce qu'on a.
À retenir :
Une identité sur les C(n,k) se démontre en spécialisant le binôme : a=b=1 donne 2ⁿ, a=1 et b=-1 donne 0, et l'identification de coefficients donne le reste.
👉 Et vérifier sur un petit cas avant de rédiger : n=4 ou n=5 prend dix secondes et confirme qu'on n'a pas inversé un indice.