Formule de Faulhaber

${\displaystyle 1^{0}+2^{0}+3^{0}+\cdots +n^{0}=n}$

${\displaystyle 1+2+3+\cdots +n={n^{2}+n \over 2}={n(n+1) \over 2}}$

${\displaystyle 1^{2}+2^{2}+3^{2}+\cdots +n^{2}={2n^{3}+3n^{2}+n \over 6}={n(n+1)(2n+1) \over 6}}$

${\displaystyle 1^{3}+2^{3}+3^{3}+\cdots +n^{3}={n^{4}+2n^{3}+n^{2} \over 4}={n^{2}(n+1)^{2} \over 4}={(1+2+3+\cdots +n)^{2}}}$ (Théorème de Nicomaque)

${\displaystyle 1^{4}+2^{4}+3^{4}+\cdots +n^{4}={6n^{5}+15n^{4}+10n^{3}-n \over 30}={n(n+1)(2n+1)(3n^{2}+3n-1) \over 30}}$

${\displaystyle 1^{5}+2^{5}+3^{5}+\cdots +n^{5}={2n^{6}+6n^{5}+5n^{4}-n^{2} \over 12}={n^{2}(n+1)^{2}(2n^{2}+2n-1) \over 12}}$

${\displaystyle 1^{6}+2^{6}+3^{6}+\cdots +n^{6}={6n^{7}+21n^{6}+21n^{5}-7n^{3}+n \over 42}={n(n+1)(2n+1)(3n^{4}+6n^{3}-3n+1) \over 42}}$

On peut voir la formule énoncée avec des termes allant de 0 à n – 1 plutôt que de 1 à n. Dans ce cas, la seule chose qui change est que l'on prend B₁ = −1/2 au lieu de +1/2, donc le terme de deuxième plus haut degré dans chaque cas possède un signe moins au lieu d'un signe plus [3].

${\displaystyle \sum _{k=0}^{n-1}k^{p}={1 \over p+1}\sum _{j=0}^{p}{p+1 \choose j}B_{j}n^{p+1-j}}$ (avec ${\displaystyle B_{1}=-{\tfrac {1}{2}}}$).

La formule est valide pour tous entiers naturels p et n (y compris pour p = 0 , avec 0⁰ = 1) :

On peut écrire (pour p et n entiers naturels) :

${\displaystyle S_{n}^{p}=\sum _{k=0}^{n}k^{p}={\frac {B_{p+1}(n+1)-B_{p+1}(0)}{p+1}}}$,

où ${\displaystyle B_{p}(X)}$ est le polynôme de Bernoulli de rang p.

${\displaystyle B_{0}(X)=1}$

${\displaystyle B_{1}(X)=X-{\tfrac {1}{2}}}$

${\displaystyle B_{2}(X)=X^{2}-X+{\tfrac {1}{6}}}$

${\displaystyle B_{3}(X)=X^{3}-{\tfrac {3}{2}}X^{2}+{\tfrac {1}{2}}X}$

On a ${\displaystyle B_{p}(0)=B_{p}}$, nombre de Bernoulli de rang p (avec ${\displaystyle B_{1}(0)=-{\tfrac {1}{2}}}$).

Dans le calcul ombral classique, on traite formellement les indices j dans une suite B_j comme s'ils étaient des exposants, c’est-à-dire que, dans ce cas, on applique la formule du binôme de Newton, ce qui donne

${\displaystyle \sum _{k=1}^{n}k^{p}={1 \over p+1}\sum _{j=0}^{p}{p+1 \choose j}B_{j}n^{p+1-j}={1 \over p+1}\sum _{j=0}^{p}{p+1 \choose j}B^{j}n^{p+1-j}={(B+n)^{p+1}-B^{p+1} \over p+1}}$.

Dans le calcul ombral « moderne », on considère la forme linéaire T sur l'espace vectoriel des polynômes de variable b donnée par

${\displaystyle T(b^{j})=B_{j}}$.

On peut alors écrire

${\displaystyle \sum _{k=1}^{n}k^{p}={1 \over p+1}\sum _{j=0}^{p}{p+1 \choose j}B_{j}n^{p+1-j}={1 \over p+1}\sum _{j=0}^{p}{p+1 \choose j}T(b^{j})n^{p+1-j}}$

${\displaystyle ={1 \over p+1}T\left(\sum _{j=0}^{p}{p+1 \choose j}b^{j}n^{p+1-j}\right)=T\left({(b+n)^{p+1}-b^{p+1} \over p+1}\right).}$

Les sommes ${\displaystyle S_{n}^{p}=\sum _{k=0}^{n}k^{p}}$ peuvent se calculer de proche en proche grâce à la relation :

${\displaystyle (p+1)S_{n}^{p}=(n+1)^{p+1}-\sum _{q=0}^{p-1}{\binom {p+1}{q}}S_{n}^{q}}$.

Par exemple, on a ${\displaystyle S_{n}^{0}=0^{0}+1^{0}+2^{0}+3^{0}+\cdots +n^{0}=n+1}$ ;

donc, ${\displaystyle 2S_{n}^{1}=(n+1)^{2}-(n+1)=n(n+1)}$,

puis ${\displaystyle 3S_{n}^{2}=(n+1)^{3}-(n+1)-{\frac {3n(n+1)}{2}}={\frac {n+1}{2}}(2n^{2}+4n+2-2-3n)={\frac {n(n+1)(2n+1)}{2}}}$,

etc.

Elle s'écrit :

${\displaystyle 2(p+1)S_{n}^{2p+1}=(n(n+1))^{p+1}-2\sum _{1\leqslant q\leqslant p/2}{\binom {p+1}{2q+1}}S_{n}^{2p+1-2q}}$.

En faisant ${\displaystyle p=1}$, on obtient par exemple directement que ${\displaystyle 4S_{n}^{3}=(n(n+1))^{2}}$.

Cette relation permet également de montrer par récurrence que ${\displaystyle S_{n}^{2p+1}}$ est un polynôme de degré ${\displaystyle p+1}$ en ${\displaystyle n(n+1)}$.

Elle s'écrit, pour p strictement positif :

${\displaystyle (4p+2)S_{n}^{2p}=n^{p}(n+1)^{p}(2n+1)-\sum _{1\leqslant q\leqslant p/2}\left(4{\binom {p}{2q+1}}+2{\binom {p}{2q}}\right)S_{n}^{2p-2q}}$.

En faisant ${\displaystyle p=1}$, on obtient par exemple directement que ${\displaystyle 6S_{n}^{2}=n(n+1)(2n+1)}$.

Cette relation permet également de montrer par récurrence que ${\displaystyle S_{n}^{2p}}$ est le produit de ${\displaystyle (2n+1)}$ par un polynôme de degré p en ${\displaystyle n(n+1)}$.

La relation de récurrence forte vue plus haut peut s'écrire :

${\displaystyle \sum _{q=0}^{p}{\binom {p+1}{q}}S_{n}^{q}=(n+1)^{p+1}}$.

Ces relations, pour p variant de 0 à q, constituent un système triangulaire dont les solutions sont ${\displaystyle S_{n}^{0},S_{n}^{1},\cdots ,S_{n}^{q}}$.

Si ${\displaystyle A_{q+1}}$ est la matrice carrée triangulaire inférieure d'ordre q+1 définie par ${\displaystyle A_{q+1}(i,j)={\binom {i+1}{j}}}$ (les indices variant de 0 à q), le système s'écrit[4] :

${\displaystyle A_{q+1}{\begin{pmatrix}S_{n}^{0}\\S_{n}^{1}\\\cdots \\S_{n}^{q}\end{pmatrix}}={\begin{pmatrix}n+1\\(n+1)^{2}\\\cdots \\(n+1)^{q+1}\end{pmatrix}}}$

On en déduit :

${\displaystyle {\begin{pmatrix}S_{n}^{0}\\S_{n}^{1}\\\cdots \\S_{n}^{q}\end{pmatrix}}=A_{q+1}^{-1}{\begin{pmatrix}n+1\\(n+1)^{2}\\\cdots \\(n+1)^{q+1}\end{pmatrix}}}$.

Par exemple, ${\displaystyle A_{7}={\begin{pmatrix}1&0&0&0&0&0&0\\1&2&0&0&0&0&0\\1&3&3&0&0&0&0\\1&4&6&4&0&0&0\\1&5&10&10&5&0&0\\1&6&15&20&15&6&0\\1&7&21&35&35&21&7\\\end{pmatrix}}}$, et ${\displaystyle A_{7}^{-1}={\begin{pmatrix}1&0&0&0&0&0&0\\-{1 \over 2}&{1 \over 2}&0&0&0&0&0\\{1 \over 6}&-{1 \over 2}&{1 \over 3}&0&0&0&0\\0&{1 \over 4}&-{1 \over 2}&{1 \over 4}&0&0&0\\{-{1 \over 30}}&0&{1 \over 3}&-{1 \over 2}&{1 \over 5}&0&0\\0&{-{1 \over 12}}&0&{5 \over 12}&-{1 \over 2}&{1 \over 6}&0\\{1 \over 42}&0&{-{1 \over 6}}&0&{1 \over 2}&-{1 \over 2}&{1 \over 7}\end{pmatrix}}}$.

On retrouve bien ${\displaystyle S_{n}^{0}=n+1}$, ${\displaystyle S_{n}^{1}={\frac {(n+1)n}{2}}}$, etc.

La matrice ${\displaystyle A_{q+1}}$ est la matrice obtenue en tronquant la diagonale principale d'une matrice de Pascal et en enlevant la première ligne devenue nulle. La première colonne de la matrice inverse donne les nombres de Bernoulli.

La relation ci-dessus sur les sommes à exposants impairs peut aussi s'écrire :

${\displaystyle \sum _{{(i+1)}/2\leqslant j\leqslant i}2{\binom {i}{2j-i-1}}S_{n}^{2j-1}=(n(n+1))^{i}}$.

Ces relations pour i de 1 à p constituent un système triangulaire dont sont solutions ${\displaystyle S_{n}^{1},S_{n}^{3},\cdots ,S_{n}^{2p-1}}$.

Si ${\displaystyle B_{p}}$ est la matrice carrée triangulaire inférieure d'ordre p définie par ${\displaystyle B_{p}(i,j)=2{\binom {i}{2j-i-1}}}$, le système s'écrit

${\displaystyle B_{p}{\begin{pmatrix}S_{n}^{1}\\S_{n}^{3}\\\cdots \\S_{n}^{2p-1}\end{pmatrix}}={\begin{pmatrix}n(n+1)\\n^{2}(n+1)^{2}\\\cdots \\n^{p}(n+1)^{p}\end{pmatrix}}}$ ; on en déduit ${\displaystyle {\begin{pmatrix}S_{n}^{1}\\S_{n}^{3}\\\cdots \\S_{n}^{2p-1}\end{pmatrix}}=B_{p}^{-1}{\begin{pmatrix}n(n+1)\\n^{2}(n+1)^{2}\\\cdots \\n^{p}(n+1)^{p}\end{pmatrix}}}$.

Par exemple, ${\displaystyle B_{4}=2{\begin{pmatrix}1&0&0&0\\0&2&0&0\\0&1&3&0\\0&0&4&4\\\end{pmatrix}}}$, et ${\displaystyle B_{4}^{-1}={\begin{pmatrix}{1 \over 2}&0&0&0\\0&{1 \over 4}&0&0\\0&{-1 \over {12}}&{1 \over 6}&0\\0&{1 \over {12}}&{-1 \over 6}&{1 \over 8}\end{pmatrix}}}$.

On retrouve bien ${\displaystyle S_{n}^{1}=n(n+1)/2}$, ${\displaystyle S_{n}^{3}={\frac {n^{2}(n+1)^{2}}{4}}}$, ${\displaystyle S_{n}^{5}={{n^{3}(n+1)^{3}} \over 6}-{\frac {n^{2}(n+1)^{2}}{12}}}$ etc.

La matrice ${\displaystyle B_{p}}$ est le double de la matrice obtenue en tronquant une diagonale descendante sur deux de la matrice de Pascal triangulaire inférieure.

Pour tous ${\displaystyle m}$, ${\displaystyle q}$, ${\displaystyle n}$, ${\displaystyle p\in \mathbb {N} }$ tels que ${\displaystyle n\geqslant q+m-1,m\geqslant 1}$, la somme multiple de puissances ${\displaystyle p}$ distinctes, d'ordre ${\displaystyle m}$ et de bornes ${\displaystyle q}$ et ${\displaystyle n}$, est définie par

${\displaystyle \sigma _{m}(q^{p},\cdots ,n^{p})=\sum _{q\leqslant k_{1}<\cdots <k_{m}\leqslant n}k_{m}^{p}\cdots k_{1}^{p},}$

ce qui correspond à la somme des ${\displaystyle {\binom {n-q+1}{m}}}$ produits de ${\displaystyle m}$ entiers distincts entre ${\displaystyle q}$ et ${\displaystyle n}$ élevés à la même puissance ${\displaystyle p}$.

Ces sommes multiples de puissances peuvent être exprimées sous la forme d'une combinaison de sommes simples de puissances, comme illustré par le théorème suivant [5].

Théorème — Pour tout ${\displaystyle m}$, ${\displaystyle q}$, ${\displaystyle n}$, ${\displaystyle p\in \mathbb {N} }$ tels que ${\displaystyle n\geqslant q+m-1,m\geqslant 1}$, on a

$${\displaystyle \sum _{q\leqslant k_{1}<\cdots <k_{m}\leqslant n}k_{m}^{p}\cdots k_{1}^{p}=(-1)^{m}\sum _{y_{1}+\cdots +y_{m}=m}{\prod _{i=1}^{m}{{\frac {(-1)^{y_{i}}}{y_{i}!i^{y_{i}}}}{\biggl (}\sum _{k=q}^{n}{k^{ip}}{\biggl )}^{y_{i}}}}.}$$

L’application de la formule de Faulhaber pour des sommes simples de puissances conduit à la formule de Faulhaber généralisée suivante[5].

Théorème — Pour tout ${\displaystyle m}$, ${\displaystyle n}$, ${\displaystyle p\in \mathbb {N} }$ tels que ${\displaystyle n\geqslant m\geqslant 1}$, on a

$${\displaystyle \sum _{1\leqslant k_{1}<\cdots <k_{m}\leqslant n}k_{m}^{p}\cdots k_{1}^{p}=(-1)^{m}\sum _{y_{1}+\cdots +y_{m}=m}{\prod _{i=1}^{m}{{\frac {(-1)^{y_{i}}}{y_{i}!i^{y_{i}}}}{\biggl (}{{\frac {n^{ip+1}}{ip+1}}\sum _{j=0}^{ip}{(-1)^{j}{\binom {ip+1}{j}}{\frac {B_{j}}{n^{j}}}}}{\biggl )}^{y_{i}}}}.}$$

Exemples

${\displaystyle \sum _{1\leqslant k_{1}<k_{2}\leqslant n}k_{2}k_{1}={\frac {n(n-1)(n+1)(3n+2)}{24}}={\binom {n+1}{3}}{\frac {3n+2}{4}},}$ suite A000914 de l'OEIS

${\displaystyle \sum _{1\leqslant k_{1}<k_{2}\leqslant n}k_{2}^{2}k_{1}^{2}={\frac {n(n-1)(n+1)(2n-1)(2n+1)(5n+6)}{360}}={\binom {2n+2}{5}}{\frac {5n+6}{4!}},}$ suite A000596 de l'OEIS

${\displaystyle \sum _{1\leqslant k_{1}<k_{2}<k_{3}\leqslant n}k_{3}^{2}k_{2}^{2}k_{1}^{2}={\binom {2n+2}{7}}{\frac {35n^{2}+91n+60}{144}},}$ suite A000597 de l'OEIS.

Notons que pour p =1, ${\displaystyle \sum _{1\leqslant k_{1}<\cdots <k_{m}\leqslant n}k_{m}\cdots k_{1}=(-1)^{m}s(n+1,n+1-m)}$, où ${\displaystyle s(.,.)}$ représente un nombre de Stirling de première espèce.

Pour tout ${\displaystyle m}$, ${\displaystyle q}$, ${\displaystyle n}$, ${\displaystyle p\in \mathbb {N} }$, cette somme de puissances ${\displaystyle p}$ d'ordre ${\displaystyle m}$ avec des bornes ${\displaystyle q}$ et ${\displaystyle n}$ est définie par

${\displaystyle \sum _{q\leqslant k_{1}\leqslant \cdots \leqslant k_{m}\leqslant n}k_{m}^{p}\cdots k_{1}^{p}=\sum _{k_{m}=q}^{n}{\sum _{k_{m-1}=q}^{k_{m}}{\cdots \sum _{k_{1}=q}^{k_{2}}{k_{m}^{p}\cdots k_{1}^{p}}}}}$ ,

ce qui correspond à la somme des ${\displaystyle \left({\binom {n-q+1}{m}}\right)}$ produits de ${\displaystyle m}$ entiers entre ${\displaystyle q}$ et ${\displaystyle n}$ , avec répétitions possibles, élevés à la puissance ${\displaystyle p}$.

Ces sommes multiples de puissances peuvent être exprimées sous la forme d’une combinaison de sommes simples de puissances, comme illustré par le théorème suivant [6].

Théorème — Pour ${\displaystyle m}$, ${\displaystyle q}$, ${\displaystyle n}$, ${\displaystyle p\in \mathbb {N} }$ tels que ${\displaystyle n\geqslant q,m\geqslant 1}$, on a

$${\displaystyle \sum _{q\leqslant k_{1}\leqslant \cdots \leqslant k_{m}\leqslant n}k_{m}^{p}\cdots k_{1}^{p}=\sum _{y_{1}+\cdots +y_{m}=m}{\prod _{i=1}^{m}{{\frac {1}{y_{i}!i^{y_{i}}}}{\biggl (}\sum _{k=q}^{n}{k^{ip}}{\biggl )}^{y_{i}}}}.}$$

Une conséquence directe de ce théorème est la formule de Faulhaber généralisée suivante [6].

Théorème — Pour tout ${\displaystyle m}$, ${\displaystyle n}$, ${\displaystyle p\in \mathbb {N} }$ tels que ${\displaystyle m,n\geqslant 1}$, on a

$${\displaystyle \sum _{1\leqslant k_{1}\leqslant \cdots \leqslant k_{m}\leqslant n}k_{m}^{p}\cdots k_{1}^{p}=\sum _{y_{1}+\cdots +y_{m}=m}{\prod _{i=1}^{m}{{\frac {1}{y_{i}!i^{y_{i}}}}{\biggl (}{{\frac {n^{ip+1}}{ip+1}}\sum _{j=0}^{ip}{(-1)^{j}{\binom {ip+1}{j}}{\frac {B_{j}}{n^{j}}}}}{\biggl )}^{y_{i}}}}.}$$

Exemples

${\displaystyle \sum _{1\leqslant k_{1}\leqslant k_{2}\leqslant n}k_{2}k_{1}={\frac {n(n+1)(n+2)(3n+1)}{24}}={\binom {n+2}{3}}{\frac {3n+1}{4}},}$ suite A001296 de l'OEIS.

${\displaystyle \sum _{1\leqslant k_{1}\leqslant k_{2}\leqslant n}k_{2}^{2}k_{1}^{2}={\frac {n(n+1)(n+2)(2n+1)(2n+3)(5n-1)}{360}}={\binom {2n+4}{5}}{\frac {5n-1}{4!}},}$ suite A060493 de l'OEIS.

${\displaystyle \sum _{1\leqslant k_{1}\leqslant k_{2}\leqslant k_{3}\leqslant n}k_{3}^{2}k_{2}^{2}k_{1}^{2}={\binom {2n+6}{7}}{\frac {35n^{2}-21n+4}{144}},}$ suite A351105 de l'OEIS.