Prouver des identités combinatoires

Énoncé

Démontrer les identités suivantes : a) _{k=0}^{n} (-1)^k n{k} = 0 pour n 1. b) _{k=0}^{n} k\,n{k} = n 2^{n-1}. c) n{0}^2 + n{1}^2 + + n{n}^2 = 2n{n}.

Indice : a) Utiliser le binôme avec a=1, b=-1. b) Utiliser la formule d'absorption kn{k} = nn-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 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 : [formule] (car 1^{n-k} = 1 quel que soit l'exposant) Or le membre de gauche vaut 0^n = 0 pour n 1 : [formule] ⚠️ La condition n 1 n'est pas une précaution rhétorique : pour n = 0, la somme se réduit à 0{0} = 1, et 0^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)^kn{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 : kn{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)!} = nn-1{k-1} (car (n-1) - (k-1) = n-k, l'exposant du dénominateur est bien le bon) [formule] 👉 Trois lignes de calcul sur des factorielles — rien d'autre. Il n'y avait aucune raison de citer un nom.

   kn{k} = nn-1{k-1}

4. Étape 4 : On l'applique à la somme. Le terme k=0 est nul (il vaut 0 n{0}), on peut donc démarrer à k=1 : _{k=0}^{n}kn{k} = _{k=1}^{n}nn-1{k-1} = n_{k=1}^{n}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}n-1{j} Et cette somme vaut 2^{n-1} (c'est l'identité _k m{k} = 2^m avec m = n-1) : [formule] ℹ️ Contrôle sur n = 5 : 0 + 5 + 2(10) + 3(10) + 4(5) + 5(1) = 5+20+30+20+5 = 80, et 5 2^4 = 80 ✓

   _{k=0}^{n}kn{k} = n\,2^{n-1}

5. Étape 5 : c) Le principe : une même quantité comptée de deux façons. On part de l'égalité évidente (1+x)^n (1+x)^n = (1+x)^{2n}, et l'on compare le coefficient de x^n des deux côtés. À droite, par le binôme appliqué à (1+x)^{2n} : le coefficient de x^n est 2n{n}. À gauche, on développe chaque facteur. Un terme en x^n s'obtient en prenant x^k dans le premier facteur et x^{n-k} dans le second, pour un k allant de 0 à n. Le coefficient total est donc la somme de tous ces produits : _{k=0}^{n}n{k}n{n-k} Et par symétrie n{n-k} = n{k} : = _{k=0}^{n}n{k}^2 Les deux expressions comptant la même chose : [formule] ℹ️ Contrôle sur n=4 : 1^2+4^2+6^2+4^2+1^2 = 1+16+36+16+1 = 70, et 8{4} = 70 ✓

   _{k=0}^{n}n{k}^2 = 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 n{k} se démontre en spécialisant le binôme : a=b=1 donne 2^n, 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.