Formule d'inversion de Pascal, dénombrement des surjections et formule de Faulhaber

On démontre la formule d'inversion de Pascal : pour toutes suites de réels $(a_n)_{n \in \mathbb{N}}$ et $(b_n)_{n \in \mathbb{N}}$ vérifiant pour tout entier $n$ : \[ b_n = \sum\limits_{k = 0}^n \binom{n}{k} a_k, \] alors : \[ a_n = (-1)^n \sum\limits_{k = 0}^n (-1)^k \binom{n}{k} b_k. \] Si l'on note $S_{p, n}$ le nombre de surjections de $\{ 1, \dots , p \}$ dans $\{ 1, \dots , n \}$, on montre alors en dénombrant de deux manières différentes l'ensemble des applications de $\{ 1, \dots , p \}$ dans $\{ 1, \dots , n \}$ que : \[ S_{p, n} = (-1)^n \sum\limits_{k = 0}^n (-1)^k \binom{n}{k} k^p. \] Enfin, en dénombrant de deux manières différentes $\{ (a_0, \dots, a_p) \in \{ 1, \dots, n + 1 \}^{p + 1} \ \vert \ \forall \ 1 \leqslant k \leqslant p, a_0 > a_p \}$, on établit la formule de Faulhaber : \[ \sum\limits_{k = 1}^n k^p = \sum\limits_{k = 1}^n S_{p, k} \binom{n + 1}{k + 1}. \] En particulier, on retrouver que $\sum\limits_{k = 1}^n k^2 = \frac{n(n + 1)(2n + 1)}{6}$.