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

  1. É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.
  2. É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)

  3. É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)

  4. É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ⁿ⁻¹

  5. É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)

  6. É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.