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 : **a)** On applique le binôme de Newton avec a = 1 et b = -1 : [formule] Or (1-1)^n = 0^n = 0 pour n 1. Donc _{k=0}^{n} (-1)^k n{k} = 0. ✓
2. Étape 2 : **b)** On utilise la formule d'absorption : kn{k} = nn-1{k-1}. [formule] Où l'on a posé j = k-1 et utilisé n-1{j} = 2^{n-1}. ✓
3. Étape 3 : **c)** On utilise l'identité de Vandermonde. Dans (1+x)^n (1+x)^n = (1+x)^{2n}, le coefficient de x^n à droite est 2n{n}. À gauche, le coefficient de x^n est : [formule] (car n{n-k} = n{k} par symétrie). On obtient bien _{k=0}^{n} n{k}^2 = 2n{n}. ✓