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 \[\left\{0, \, 1, \, 2,\, 3,\ \dots \ , \, n \right\}\]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{align*}\binom{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{align*}façons de choisir deux nombres de cet ensemble qui contient \(n+1\) éléments.
D’autre part, si on choisit deux nombres dans \(\left\{0, \, 1, \, 2,\, 3,\, \dots, \, n \right\}\), 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 \(\left\{1, \, 2, \, 3, \ \dots \ , \, n\right\}\) qui comporte \(n\) éléments. Disons que ce nombre est \(k\). Le plus petit nombre peut donc être choisi dans l’ensemble suivant \[\left\{0,\, 1,\, 2,\, 3, \ \dots \ , \, k-1\right\}\]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