La somme des $n$ premiers entiers (bis)

On a déjà vu la méthode « classique » au début de ce billet, ici. Là, on s’intéresse à la version combinatoire.

On considère l’ensemble $$\{0,1,2,3,\dots ,n\}$$De combien de façons peut-on choisir deux nombres de cet ensemble qui contient $n+1$ éléments ?

D’une part, si on se rappelle nos combinaisons, il y a $$\begin{array}{rl}(\genfrac{}{}{0ex}{}{n+1}{2})& =\frac{(n+1)!}{2!(n+1-2)!}\\ \\ & =\frac{(n+1)(n)(n-1)!}{(2)(1)(n-1)!}\\ \\ & =\frac{n(n+1)}{2}\end{array}$$façons de choisir deux nombres de cet ensemble qui contient $n+1$ éléments.

D’autre part, si on choisit deux nombres dans $\{0,1,2,3,\dots ,n\}$, il y aura forcément un nombre plus grand que l’autre. Puisque $0$ ne peut être le plus grand nombre, celui-ci sera choisi dans l’ensemble $\{1,2,3,\dots ,n\}$ qui comporte $n$ éléments. Disons que ce nombre est $k$. Le plus petit nombre peut donc être choisi dans l’ensemble suivant $$\{0,1,2,3,\dots ,k-1\}$$qui comporte $k$ éléments. En d’autres mots, pour chacune des possibilités pour le plus grand nombre, il y a $k$ possibilités pour le plus petit nombre. Ainsi, le nombre de sélections possibles est donc $$\sum _{k=1}^{n}k=1+2+3+\dots +n$$

Puisqu’on a compté la même chose de deux manières différentes, on a $$\sum _{k=1}^{n}k=\frac{n(n+1)}{2}$$

Référence : Benjamin, Arthur T. et Jennifer J. Quinn, Proofs that Really Count : The Art of Combinatorial Proof, MAA Press, 2003