Voir la source de Formule de Faulhaber

En [[mathématiques]], la '''formule de Faulhaber''', portant le nom du mathématicien allemand [[Johann Faulhaber]], exprime la somme des puissances {{Mvar|p}}-ième des {{Mvar|n}} premiers entiers : <center><math>\sum_{k=1}^nk^p = 1^p + 2^p + 3^p + \cdots + n^p \qquad \left(\mbox{pour }n\in\N^*\text{ et }p\in\N\right)</math></center>par une [[fonction polynomiale]] de degré {{Mvar|p}}&nbsp;+&nbsp;1 en {{Mvar|n}}<ref>Nulle en ''n'' = 0 (cf. « [[Somme vide]] ») donc produit de ''n'' par une fonction polynomiale de degré ''p''.</ref>, les coefficients impliquant les [[Nombre de Bernoulli|nombres de Bernoulli]] : <math>B_2=\tfrac16,\quad B_4=-\tfrac1{30},\quad B_6=\tfrac1{42} \ldots</math> les nombres de Bernoulli d'indices impairs supérieurs ou égaux à trois étant nuls.
<center><math>\sum_{k=1}^nk^p =\frac1{p+1}\left(n^{p+1}+
\frac12(p+1){n^p}+\frac16{ p+1\choose2}{n^{p-1}}- 
\frac1{30}{p+1\choose4}{n^{p-3}}+\frac1{42}{p+1\choose6}{n^{p-5}}+\ldots+(p+1)B_pn\right)</math>.</center>Les coefficients <math>\textstyle{p+1 \choose j}</math> qui apparaissent sont les [[Coefficient binomial|coefficients binomiaux]] (anciennement notés <math>\mathrm{C}_{p+1}^j</math>).

== Énoncé de la formule ==
Dans la convention la plus usuelle, les [[Nombre de Bernoulli|nombres de Bernoulli]] sont <math>B_0 = 1,\quad B_1 =-\tfrac12,\quad B_2 =\tfrac16, \quad B_3 = 0,\quad B_4 = -\tfrac1{30}\quad\dots</math>
mais ici, une convention moins courante est adoptée, à savoir que le nombre <math>B_1</math> est changé en <math>+\frac12</math>.

La formule de Faulhaber s'écrit (pour <math>p\in\N</math> et <math>n\in\N^*</math>) :<center><math>\sum_{k=1}^nk^p = {1 \over p+1} \sum_{j=0}^p {p+1 \choose j} B_j n^{p+1-j}</math> (avec <math>B_1=\tfrac12</math> au lieu de <math>-\tfrac12</math>).</center>Faulhaber ne connaissait pas la formule sous cette forme, qui a été découverte par [[Jacques Bernoulli]], et qui est un cas particulier de la [[Formule d'Euler-Maclaurin|formule d’Euler-MacLaurin]]. Mais il a obtenu l'expression dans les 17 premiers cas, et le fait que lorsque l'exposant est impair, la somme s'exprime en fonction de la somme des <math>n</math> premiers entiers. Dans ses calculs, il a manipulé la factorielle ''n''! jusqu'à 24!, ce qui illustre son remarquable talent de calculateur, qu'il partage avec son correspondant [[Ludolph van Ceulen]]. Il est remarquable surtout par son anticipation des {{quoi|sommes multiples discrètes}} à une époque où l'analyse balbutie. Il utilise la ''k''-symétrie, et donne aussi certaines généralisations remarquables<ref name="Knuth2">{{Article |langue=en |prénom=Donald E. |nom=Knuth |lien auteur=Donald Knuth |titre=Johann Faulhaber and sums of powers |revue=[[Mathematics of Computation|Math. Comp.]] |vol=61 |année=1993 |url=http://www.ams.org/journals/mcom/1993-61-203/S0025-5718-1993-1197512-7/S0025-5718-1993-1197512-7.pdf |p.=277-294 }}.<!--http://arxiv.org/abs/math.CA/9207222 contient une coquille pour la somme des puissances 11-ièmes--></ref>.

=== Exemples ===
: <math>1^0 + 2^0 + 3^0 + \cdots + n^0 = n</math>
{{col-begin}}

:<math>1 \,+ \,2\, + \,3 \,+ \cdots + n = \frac12 n^2 + \frac12 n = {n(n+1) \over 2}</math>

:<math>1^2 + 2^2 + 3^2 + \cdots + n^2 =  \frac13n^3 + \frac12n^2 + \frac16n = {n(n+1)(2n+1) \over 6}</math>

:<math>1^3 + 2^3 + 3^3 + \cdots + n^3 = \frac14n^4 + \frac12n^3 + \frac14n^2  = {n^2(n+1)^2\over 4}={(1 + 2 + 3 + \cdots + n)^2}</math> ([[Théorème de Nicomaque]])

:<math>1^4 + 2^4 + 3^4 + \cdots + n^4 = \frac15n^5 + \frac12n^4 + \frac13n^3 - \frac1{30}n  = {n(n+1)(2n+1)(3n^2+3n-1) \over 30} </math>

:<math>1^5 + 2^5 + 3^5 + \cdots + n^5 = \frac16n^6 + \frac12n^5 + \frac5{12}n^4 - \frac1{12}n^2  = {n^2(n+1)^2(2n^2+2n-1) \over 12}  </math>

:<math>1^6 + 2^6 + 3^6 + \cdots + n^6 = \frac17n^7 + \frac12n^6 + \frac12n^5 -\frac16n^3 + \frac1{42}n  = {n(n+1)(2n+1)(3n^4+6n^3-3n+1) \over 42} </math>
{{col-end}}

=== Une autre forme ===
On peut voir la formule énoncée avec des termes allant de 0 à {{Mvar|n}}&nbsp;–&nbsp;1 plutôt que de 1 à {{Mvar|n}}<ref>{{Ouvrage|langue=en|auteur1=Ronald Graham,Donald Knuth, Oren Patashnik|titre=Mathématiques concrètes|éditeur=Thomson publishing|année=1998|passage=300 - 303}}</ref>. Dans ce cas, la ''seule'' chose qui change est que l'on prend ''B''<sub>1</sub>&nbsp;=&nbsp;−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<ref>Ceci vient de ce que <math>\sum_{k=1}^{n-1}k^p=\sum_{k=1}^{n}k^p-n^p</math>, ce qui change <math>\frac{n^p}{2}</math> en <math>-\frac{n^p}{2}</math>.</ref>.

<center><math>\sum_{k=0}^{n-1}k^p = \frac1{p+1}\left(n^{p+1}-\frac12(p+1){n^p}+\ldots+(p+1)B_pn\right)={1 \over p+1} \sum_{j=0}^p  {p+1 \choose j} B_j n^{p+1-j}</math> (avec <math>B_1=-\tfrac12</math>).</center>

La formule est valide pour tous entiers <math>p\geqslant0</math> et <math>n\geqslant1</math> (donc y compris pour  {{Mvar|p}} = 0 , avec [[Zéro puissance zéro|0{{exp|0}} = 1]]) :

{{col-begin}}
{{col-2}}
<math>0^0 +1^0 + 2^0 + 3^0 + \cdots + (n-1)^0 = n </math>

<math>0 + 1 + 2 + \cdots + (n-1) = \frac12 n^2 - \frac12 n=\frac{n(n-1)}{2} </math>

<math>0 + 1 + 2^2 + \cdots + (n-1)^2 = \frac13n^3 -\frac12n^2 + \frac16n ={n(n-1)(2n-1) \over 6}</math>

{{col-2}}
<math>0 + 1 + 2^3 + \cdots + (n-1)^3 = \frac14n^4 - \frac12n^3 + \frac14n^2=\frac{n^2(n-1)^2}{4} </math>

<math>0 + 1 + 2^4 + \cdots + (n-1)^4 = \frac15n^5 - \frac12n^4 + \frac13n^3 - \frac1{30}n  </math>

<math>0 + 1 + 2^5 + \cdots + (n-1)^5 =  \frac16n^6 -\frac12n^5 + \frac5{12}n^4 - \frac1{12}n^2 </math>
{{col-end}}

=== Relation avec les polynômes de Bernoulli ===
Définissons pour {{Mvar|p}} et {{Mvar|n}} [[Entier naturel|entiers naturels]] : <math>S_n^p=\sum_{k=0}^nk^p </math>, donc <math>S_n^0=n+1 </math> et <math>S_n^p=\sum_{k=1}^nk^p</math> pour <math>n,p\geqslant1</math>.

On a alors pour tout <math>n,p\geqslant0</math>:<center><math>S_n^p= \frac{B_{p+1}(n+1)-B_{p+1}(0)}{p+1}</math>,</center>où <math>B_p(X)</math> est le [[polynôme de Bernoulli]] de rang {{Mvar|p}}.

: <math>B_0(X)=1</math>
: <math>B_1 (X)=X-\tfrac12</math>
: <math>B_2(X)=X^2-X+\tfrac16</math>
: <math>B_3(X)=X^3-\tfrac32X^2+\tfrac12X</math>

On a <math>B_p(0)=B_p</math>, [[nombre de Bernoulli]] de rang {{Mvar|p}} (avec <math>B_1(0)=-\tfrac12</math>).

{{Démonstration|Ceci provient du fait que pour tout <math>p\geqslant0</math>:
:<math>B_{p+1}(X+1)-B_{p+1}(X)=(p+1)X^{p}</math>   (1).
Or par [[Série télescopique|télescopage]] :
:<math>A=\sum_{k=0}^n(B_{p+1}(k+1)-B_{p+1}(k))=B_{p+1}(n+1)-B_{p+1}(0) </math>,
donc par (1) :
:<math>A=(p+1)\sum_{k=0}^nk^p=(p+1)S_n^p </math>, pour <math>p\geqslant0</math>
d'où la formule.
}}

=== Forme symbolique ===

Dans le [[calcul ombral]] classique, on traite formellement les indices <math>j</math> dans l'expression <math>B_j</math> 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, pour <math>n,p\geqslant1</math> :
:<math>\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}</math>.

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

:<math>T(b^j) = B_j</math>.

On peut alors écrire

:<math>\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} </math>

:::<math> = {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). </math>

== Polynômes de Faulhaber ==
Faulhaber a observé (sans en donner de preuve) que 
* si {{math|''p''}} est impair, alors <math>1^p + 2^p + 3^p + \cdots + n^p</math> est une fonction polynomiale de <math>y=1+2+3+\cdots+n ={n^2+n\over 2}</math>,
* si {{math|''p''}} est pair, alors <math>1^p + 2^p + 3^p + \cdots + n^p</math> est le produit de <math>2n+1</math> par une fonction polynomiale de {{math|''y''}}.

Ces propriétés se montrent en utilisant respectivement les [[#Relation de récurrence forte sur les sommes de degré impair|relations de récurrence forte sur les sommes de degré impair]] et les [[#Relation de récurrence forte sur les sommes de degré pair|relations de récurrence forte sur les sommes de degré pair]].

Ainsi, pour {{math|''p''}} impair :
:<math>1^3 + 2^3 + 3^3 + \cdots + n^3 = y^2</math>
:<math>1^5 + 2^5 + 3^5 + \cdots + n^5 = {4y^3 - y^2 \over 3}</math>
:<math>1^7 + 2^7 + 3^7 + \cdots + n^7 = {6y^4 -4y^3 + y^2 \over 3}</math> 
:::(et donc <math>1^5 + 2^5 + 3^5 + \cdots + n^5 +1^7 + 2^7 + 3^7 + \cdots + n^7 =2y^4</math>)
:<math>1^9 + 2^9 + 3^9 + \cdots + n^9 = {16y^5 - 20y^4 +12y^3 - 3y^2 \over 5}</math>
:<math>1^{11} + 2^{11} + 3^{11} + \cdots + n^{11} = {16y^6 - 32y^5 + 34y^4 - 20y^3 + 5y^2 \over 3}</math>

et pour {{math|''p''}} pair :
:<math>1^2 + 2^2 + 3^2 + \cdots + n^2 = (2n+1) \frac{y}{3}</math>
:<math>1^4 + 2^4 + 3^4 + \cdots + n^4 = (2n+1) \frac{6y^2-y}{15}</math>
:<math>1^6 + 2^6 + 3^6 + \cdots + n^6 = (2n+1) \frac{12y^3-6y^2+y}{15}</math>
:<math>1^8 + 2^8 + 3^8 + \cdots + n^8 = (2n+1) \frac{40y^4-40y^3+18y^2-3y}{45}</math>

Quelques auteurs<ref name=Edward>{{article|auteur=A. W. F. Edwards|titre=Sums of powers of integers: a little of the history|périodique=Math. Gazette|numéro=66|année=1982|pages=22-28|langue=en}}</ref> appellent ces polynômes <math>P(y)</math>, avec <math>y = \frac{n(n+1)}2</math>, « polynômes de Faulhaber » ; [[Donald Knuth]] a donné des démonstrations de ces résultats (et d'autres les généralisant encore) en n'utilisant que des méthodes que Faulhaber maîtrisait<ref name="Knuth2" />.

== Expression utilisant les nombres de Stirling de seconde espèce ==
Pour tout <math>p\geqslant 1</math>, on a la relation :

<center><math>\sum_{k=0}^nk^p=\sum_{i=1}^p\frac{S(p,i)}{i+1}(n+1)_{i+1}</math></center>  

où les <math>S(p,i)</math> sont les [[Nombre de Stirling#Nombre de Stirling de seconde esp%C3%A8ce|nombres de Stirling de seconde espèce]] (nombre de partitions en ''i'' parties d'un ensemble à {{Mvar|p}} éléments) et <math>(n+1)_{i+1}=(n+1)(n)...(n+1-i)</math> ([[symbole de Pochhammer]]).

{{Démonstration|1=On utilise la [[Nombre de Stirling#Caractérisation algébrique|caractérisation algébrique <math>\sum_{i=1}^pS(p,i)(X)_i=X^p</math>]].

Alors [[Nombre de Stirling#Caractérisation algébrique|<math>\sum_{k=0}^n k^p=\sum_{k=0}^n \sum_{i=1}^pS(p,i)(k)_i=\sum_{i=1}^p S(p,i)\sum_{k=0}^n (k)_i</math>]].

Or <math>(k)_i=\frac{1}{i+1}((k+1)_{i+1}-(k)_{i+1})</math>, donc par télescopage, <math>\sum_{k=0}^n (k)_i=\frac{1}{i+1}((n+1)_{i+1}-0)</math>. On obtient ainsi la formule annoncée.}}

Par exemple <math>\sum_{k=0}^nk=\frac{1}{2}(n+1)n</math>, et <math>\sum_{k=0}^nk^2=\frac{1}{2}(n+1)n+\frac{1}{3}(n+1)n(n-1)</math>.

== Relations de récurrence liant ces sommes ==
 
=== Relation de récurrence forte (Pascal, 1655) ===
Pour <math>n,p\geqslant0</math>, les sommes <math>S_n^p=\sum_{k=0}^n k^p</math> peuvent se calculer de proche en proche grâce à la relation<ref>{{ouvrage|lang=la, fr|auteur=Blaise Pascal|titre=Œuvres complètes de Pascal, Potestatum Numericarum Summa|éditeur=Gallimard, collection de la Pléiade|année=1665, 1954|passage=166,1427}}</ref>:
<center><math>(p+1)S_n^p=(n+1)^{p+1}-\sum_{q=0}^{p-1}\binom{p+1}{q}S_n^q </math>.</center>

{{Démonstration|Par [[Série télescopique|télescopage]] : 
:<math>\sum_{k=0}^{n}((k+1)^{p+1}-k^{p+1})=(n+1)^{p+1}</math>
et par la [[formule du binôme]] :
:<math>\sum_{k=0}^{n}((k+1)^{p+1}-k^{p+1})=\sum_{k=0}^{n}\sum_{q=0}^{p}\binom{p+1}{q} k^q
=\sum_{q=0}^{p}\binom{p+1}{q}\sum_{k=0}^{n}k^q=(p+1)S_n^p+\sum_{q=0}^{p-1}\binom{p+1}{q} S_n^q</math>
d'où la formule annoncée.}}

Par exemple, on a <math>S_n^0=0^0+1^0 + 2^0 + 3^0 + \cdots + n^0 = n+1</math> ;

donc, <math>2S_n^1=(n+1)^2-(n+1)=n(n+1)</math>,

puis <math>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}</math>,

etc.

=== Relation de récurrence forte sur les sommes de degré impair ===
Elle s'écrit :
<center><math>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} </math>.</center>

{{Démonstration|La démonstration est similaire à la précédente. On procède par télescopage : 
:<math>A_n=\sum_{k=1}^{n}((k(k+1))^{p+1}-(k(k-1))^{p+1})=(n(n+1))^{p+1}</math>,
et par la [[formule du binôme]] :
:<math>A_n=\sum_{k=1}^{n}k^{p+1}\sum_{q=0}^{p+1}\binom{p+1}{q}(1-(-1)^q)k^{p+1-q}
=\sum_{k=1}^{n}k^{p+1}\sum_{0\leqslant 2q+1\leqslant p+1}\binom{p+1}{2q+1}2k^{p+1-2q-1}
</math>
donc :
:<math>A_n=\sum_{0\leqslant 2q+1\leqslant p+1}\sum_{k=1}^{n}\binom{p+1}{2q+1}2k^{2p+1-2q}
=\sum_{0\leqslant q\leqslant p/2}\binom{p+1}{2q+1}2S_n^{2p+1-2q}
=2(p+1)S_n^{2p+1}+2\sum_{1\leqslant q\leqslant p/2}\binom{p+1}{2q+1}S_n^{2p+1-2q}</math> 
d'où la formule annoncée.}}

En faisant <math>p=1</math>, on obtient par exemple directement que  <math>4S_n^3=(n(n+1))^2</math>.

Cette relation permet également de montrer par récurrence que <math>S_n^{2p+1}</math> est un polynôme de degré <math>p+1</math> en <math>n(n+1)</math>.

=== Relation de récurrence forte sur les sommes de degré pair ===
Elle s'écrit, pour {{math|''p''}} strictement positif :
<center><math>(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} </math>.</center>

{{Démonstration|La démonstration est similaire à la précédente. On procède par télescopage : 
:<math>A_n=\sum_{k=1}^{n}(k^p(k+1)^p(2k+1)-(k-1)^pk^p(2k-1))=n^p(n+1)^p(2n+1)</math>,
et par la [[formule du binôme]] :
:<math>A_n=\sum_{k=1}^{n}k^p\sum_{q=0}^p\binom{p}{q}(k^{p-q}(2k+1)-(-1)^qk^{p-q}(2k-1))
=\sum_{k=1}^{n}k^p \left(\sum_{q\, \rm{impair}} \binom{p}{q} 4k^{p-q+1} + \sum_{q\, \rm{pair}} \binom{p}{q} 2k^{p-q}\right)</math>
donc
:<math>A_n=\sum_{k=1}^{n}k^p \left(\sum_{q\, \rm{pair}} \binom{p}{q+1} 4k^{p-q} + \sum_{q\, \rm{pair}} \binom{p}{q} 2k^{p-q}\right)
</math>
donc :
:<math>A_n=\sum_{0\leqslant q\leqslant p/2}\sum_{k=1}^{n}\left(4\binom{p}{2q+1} + 2\binom{p}{2q}\right) k^{2p-2q}
=\sum_{0\leqslant q\leqslant p/2}\left(4\binom{p}{2q+1} + 2\binom{p}{2q}\right) S_n^{2p-2q}</math> 
d'où la formule annoncée.}}

En faisant <math>p=1</math>, on obtient par exemple directement que  <math>6S_n^2=n(n+1)(2n+1)</math>.

Cette relation permet également de montrer par récurrence que <math>S_n^{2p}</math> est le produit de <math>(2n+1)</math> par un polynôme de degré {{math|''p''}} en <math>n(n+1)</math>.

== Expressions matricielles des formules de Faulhaber ==

=== Pour les sommes quelconques ===

==== Première forme ====
La [[#Relation de récurrence forte (Pascal 1655)|relation de récurrence forte]] de Pascal vue plus haut peut s'écrire :
{{Centrer|<math>\sum_{q=0}^p\binom{p+1}{q}S_n^q=(n+1)^{p+1}</math>.}}

Ces relations, pour {{Mvar|p}} variant de 0 à {{Mvar|q}}, constituent un système triangulaire dont les solutions sont <math>S_n^0,S_n^1,\cdots,S_n^q</math>.

Si <math>A_{q+1}</math> est la [[Matrice (mathématiques)|matrice carrée]] triangulaire inférieure d'ordre {{Mvar|q}}+1 définie par <math>A_{q+1}(i,j)=\binom{i+1}{j}</math> (les indices variant de 0 à {{Mvar|q}}), le système s'écrit<ref name="Edward" /> :

:<math>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}</math>
On en déduit :
:<math>\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}</math>.

Par exemple, <math>
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}
</math>, et <math>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}</math>.

On retrouve bien <math>S_n^0=n+1</math>, <math>S_n^1=\frac{(n+1)n}{2}</math>, etc.

La matrice <math>A_{q+1}</math> 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 inversible|matrice inverse]] donne les [[nombre de Bernoulli|nombres de Bernoulli]]<ref>{{Lien web|langue=en |auteur1=Giorgio Pietrocola |titre=On polynomials for the calculation of sums of powers of successive integers and Bernoulli numbers deduced from the Pascal's triangle|date=2017|lire en ligne=http://www.pietrocola.eu/EN/Theoremsonthesumofpowersofsuccessiveintegersbygiorgiopietrocola%20.pdf}}, cité par {{Article|lang=en|auteur=Nigel Derby|titre=The continued search for sums of powers|revue=[[The Mathematical Gazette]]|date=2019|vol=103|numéro=556|p.=94-100|url=https://5c5d67a2-26fb-4beb-8f23-7e1488a50f51.filesusr.com/ugd/73c898_98fa6d9fa42b4a24aad6237fe114bc5f.pdf}}.</ref>.

==== Deuxième forme ====
La méthode précédente donne les <math>S_n^p</math>, comme polynômes en <math>n+1</math> ; on peut obtenir directement les polynômes en <math>n</math> grâce à la relation, valable pour <math>n\geqslant1</math> : {{Centrer|<math>\sum_{q=0}^{p}\left((-1)^{p+q}\binom{p+1}{q}\sum_{k=1}^{n}k^q\right)=n^{p+1} </math>.}}

{{Démonstration|Par [[Série télescopique|télescopage]]  : 
:<math>\sum_{k=1}^{n}(k^{p+1}-(k-1)^{p+1})=n^{p+1}</math>
et par la [[formule du binôme]] :
:<math>\sum_{k=1}^{n}(k^{p+1}-(k-1)^{p+1})=\sum_{k=1}^{n}\sum_{q=0}^{p}\binom{p+1}{q} k^q(-1)^{p-q}
=\sum_{q=0}^{p}\left((-1)^{p+q}\binom{p+1}{q}\sum_{k=1}^{n}k^q\right)</math>
}}


En utilisant la matrice <math>B_{q+1}</math> obtenue à partir de <math>A_{q+1}</math> en alternant les signes : <math>B_{q+1}(i,j)=(-1)^{i+j}\binom{i+1}j</math>, on obtient alors <ref>{{Lien web |langue=en |auteur1=Giorgio Pietrocola |titre=Matrices for a quick proof of the classical
problem of sums of powers of successive integers |url=http://www.pietrocola.eu/ricerchebernoulli/en/Matrices_for_a_quick_proof_of_the_classical.pdf |site=www.pietrocola.eu |date=2019}}</ref>:
:<math>\begin{pmatrix} S_n^0-1\\ S_n^1\\\cdots\\S_n^q \end{pmatrix}=B_{q+1}^{-1}
\begin{pmatrix} n\\ n^2\\\cdots\\n^{q+1} \end{pmatrix} </math>
Par exemple, <math>
B_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}
</math>, et <math>B_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}</math>.
d'où

<math>
\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}
\begin{pmatrix} 
n\\n^2\\n^3\\n^4\\n^5\\n^6\\n^7 
\end{pmatrix}=
\begin{pmatrix}
n\\
{1\over 2}n+ {1\over 2}n^2\\
{1\over 6}n +{1\over 2}n^2+{1\over 3}n^3\\
{1\over 4}n^2 +{1\over 2}n^3+ {1\over 4}n^4\\
{-{1\over 30} }n+ {1\over 3}n^3 +{1\over 2}n^4+ {1\over 5}n^5\\
{-{1\over 12}}n^2+{5\over 12}n^4 +{1\over 2}n^5+ {1\over 6}n^6\\
{1\over 42}n{-{1\over 6}}n^3+ {1\over 2}n^5+{1\over 2}n^6+{1\over 7}n^7
\end{pmatrix}</math>

=== Pour les sommes à exposants impairs ===
La relation ci-dessus sur les sommes à exposants impairs peut aussi s'écrire :{{Centrer|<math>\sum_{{(i+1)}/2\leqslant j\leqslant i}2\binom{i}{2j-i-1}S_n^{2j-1}=(n(n+1))^i</math>.}}Ces relations pour ''i'' de 1 à {{Mvar|p}} constituent un système triangulaire dont sont solutions <math>S_n^{1},S_n^{3},\cdots,S_n^{2p-1}</math>.

Si <math>B_p</math> est la matrice carrée triangulaire inférieure d'ordre {{Mvar|p}} définie par <math>B _p(i,j)=2\binom{i}{2j-i-1}</math>, le système s'écrit

<math>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}</math> ; on en déduit <math>\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}</math>.

Par exemple, <math>
B_4=2\begin{pmatrix}
 1&  0& 0 &0\\
0&  2&   0&0\\
 0& 1&   3 &0 \\
0& 0&   4 &4\\

\end{pmatrix}
</math>, et <math>
B_4^{-1}=\begin{pmatrix}
 {1 \over 2} &  0& 0 &0  \\
0&  {1\over4}&   0&0 \\
 0& {-1\over{12}}&   {1\over6}&0  \\
  0& {1\over{12}}&   {-1\over6}&{1\over8}


\end{pmatrix}
</math>.

On retrouve bien <math>S_n^1=n(n+1)/2</math>, <math>S_n^3=\frac {n^2(n+1)^2}{4}</math>, <math>
S_n^5={{n^3(n+1)^3}\over6}-\frac{n^2(n+1)^2}{12}
</math> etc.

La matrice <math>B_p</math> est le double de la matrice obtenue en tronquant une diagonale descendante sur deux de la [[matrice de Pascal]] triangulaire inférieure.

== Généralisations de la formule de Faulhaber ==
La formule de Faulhaber peut être étendue à différents types de sommes multiples de puissances : soit à des sommes de produits de puissances distinctes (mais de même exposant), soit à des sommes de produits de puissances avec répétitions possibles ; elle se généralise également à des sommes de puissances d'une progression arithmétique.

=== Sommes multiples de produits de puissances distinctes ===
Pour tous <math>m</math>, <math>q</math>, <math>n</math>, <math>p\in\mathbb{N}</math> tels que <math>n \geqslant q+m-1,m\geqslant1</math>, la somme multiple de puissances <math>p</math> distinctes, d'ordre <math>m</math> et de bornes <math>q
</math> et <math>n</math>, est définie par

<math>\sigma_m(q^p,\cdots,n^p)=\sum_{q\leqslant k_1 < \cdots < k_m \leqslant n} k_m^p \cdots k_1^p,</math>

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

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 <ref name=":0">{{Lien web |langue=en |auteur=Roudy El Haddad |titre=A generalization of multiple zeta values. Part 2: Multiple sums |url=https://nntdm.net/volume-28-2022/number-2/200-233/ |série=Notes on Number Theory and Discrete Mathematics |doi=10.7546/nntdm.2022.28.2.200-233 }}</ref>.

{{Théorème|1=Pour tout <math>m</math>, <math>q</math>, <math>n</math>, <math>p\in\mathbb{N}</math> tels que <math>n \geqslant q+m-1,m\geqslant1</math>, on a
<math display=block>\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}}}.</math>
}}
L’application de la formule de Faulhaber pour des sommes simples de puissances conduit à la formule de Faulhaber généralisée suivante<ref name=":0" />.

{{Théorème|1=Pour tout <math>m</math>, <math>n</math>, <math>p\in\mathbb{N}</math> tels que <math>n\geqslant m\geqslant1</math>, on a
<math display=block>\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}}}.</math>
}}
;Exemples
:<math>\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},</math> {{OEIS|A000914}}
:<math>\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!},</math> {{OEIS|A000596}}
:<math>\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},</math> {{OEIS|A000597}}.

Notons que pour {{Mvar|p}} =1, <math>\sum_{1\leqslant k_1 < \cdots < k_m \leqslant n} k_m \cdots k_1=(-1)^ms(n+1,n+1-m)
</math>, où <math>s(.,.)</math> représente un [[Nombre de Stirling#Nombre de Stirling de première espèce|nombre de Stirling de première espèce]].

=== Sommes multiples de produits de puissances avec répétitions possibles ===
Pour tout <math>m</math>, <math>q</math>, <math>n</math>, <math>p\in\mathbb{N}</math>, cette somme de puissances <math>p</math> d'ordre <math>m</math> avec des bornes <math>q</math> et <math>n</math> est définie par
:<math>\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}}}</math> ,

ce qui correspond à la somme des <math>\left ( \binom{n-q+1}{m}\right )</math> produits de <math>m</math> entiers entre <math>q</math> et <math>n</math> , avec [[Combinaison avec répétition|répétitions possibles]], élevés à la puissance <math>p</math>.

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 <ref name=":1">{{Lien web |langue=en |auteur=Roudy El Haddad |titre=A generalization of multiple zeta values. Part 1: Recurrent sums |url=https://nntdm.net/volume-28-2022/number-2/167-199/ |série=Notes on Number Theory and Discrete Mathematics |doi=10.7546/nntdm.2022.28.2.167-199 }}</ref>.

{{Théorème|1=Pour <math>m</math>, <math>q</math>, <math>n</math>, <math>p\in\mathbb{N}</math> tels que <math>n \geqslant q,m\geqslant1</math>, on a
<math display=block>\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}}}.</math>
}}
Une conséquence directe de ce théorème est la formule de Faulhaber généralisée suivante <ref name=":1" />.

{{Théorème|1=Pour tout <math>m</math>, <math>n</math>, <math>p\in\mathbb{N}</math> tels que <math>m,n \geqslant 1</math>, on a
<math display=block>\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}}}.</math>
}}

;Exemples
:<math>\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},</math> {{OEIS|A001296}}.
:<math>\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!},</math> {{OEIS|A060493}}.
:<math>\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},</math> {{OEIS|A351105}}.

Notons que pour {{Mvar|p}} = 1, <math>\sum_{1\leqslant k_1 \leqslant \cdots \leqslant k_m \leqslant n} k_m \cdots k_1=S(n+m,n)
</math>, où <math>S(.,.)</math> désigne un [[Nombre_de_Stirling#Nombre_de_Stirling_de_seconde_espèce|nombre de Stirling de seconde espèce]].

=== Somme de puissances d'une progression arithmétique ===
Le problème consiste donc à trouver des polynômes en fonction de ''n'' calculant

: <math>S_n^p(h,d)=\sum_{k=0}^{n-1}(h+kd)^p = h^p + (h+d)^p + \cdots + (h+(n-1)d)^p,</math>

avec ''p'' et ''n'' entiers non-négatif, ''h''  premier terme d'une [[Suite arithmétique|progression arithmétique]] et <math>d\ne 0</math> raison de la même progression, ''h'' et ''d'' étant des [[Nombre réel|nombres réels]] ou complexes quelconques, et même des éléments quelconques d'un [[Anneau (mathématiques)|anneau]].

<math>S_n^p(1,1)</math> sont les polynômes identifiés par la formule de Faulhaber présenté à titre posthume par Bernoulli en 1713<ref>{{Lien web |langue=latin |auteur1=Jacob Bernoulli |titre=Ars Conjectandi|chapitre=Summa potestatem|url=https://archive.org/details/bub_gb_kz9nvk99EWoC/page/n139/mode/2up|site=Internet Archive|date=1713}}</ref>; 

<math>S_n^p(0,1)</math>  sont les polynômes du deuxième paragraphe, différant des précédents que par le signe d'un monôme de degré ''p;''

<math>S_n^p(1,2)</math>  sont les polynômes par sommes de puissances de nombres impairs successifs.

Utilisant [[#Expression matricielle des formules de Faulhaber|la même représentation matricielle]], le cas général est résolu par la formule suivante: <math>\quad\vec{S_n}(h,d)=T(h,d)A^{-1}\vec{N}_n\quad,</math> où

<math>[\vec{S_n}(h,d)]_{r}=S_n^{r-1}(h,d),\quad  [T(h,d)]_{r,c}= \begin{cases}0, &\text{si } c>r, \\
\binom{r-1}{c-1}h^{r-c}d^{c-1}&\text{si } c\leq r.\end{cases}, \quad [A]_{r,c}=\begin{cases} 0, &\text{si }c>r, \\
\binom{r}{c-1}, &\text{si }c\leq r,\end{cases},\quad[\vec{N}_n]_r=n^{r},</math>
avec <math>\quad  1 \le r \le m \quad </math> et  <math>\quad  1 \le c \le m \quad</math></B>
où ''r'' (ligne), ''c'' (colonne) et ''m'' (ordre de la matrice) sont des entiers <ref>{{Lien web |langue=en |auteur1=Giorgio Pietrocola |titre=Binomial matrices for polynomials calculating sums of powers with bases in arithmetic progression |url=https://www.academia.edu/125139092/Binomial_matrices_for_polynomials_calculating_sums_of_powers_with_bases_in_arithmetic_progression |site=[[Academia.edu]] |date=2019}}</ref>.
==== Exemple ====
La formule dans le cas particulier <math>m=5~ (p=0,1,...,m-1)</math> devient :  

: <math>
\begin{pmatrix} 
S_n^0({h,d})\\
S_n^1({h,d})\\
S_n^2({h,d})\\
S_n^3({h,d})\\
S_n^4({h,d})
\end{pmatrix}=
\begin{pmatrix}
1& 0& 0& 0&0\\
h& d& 0& 0&0\\
h^2& 2hd& d^2& 0&0\\
h^3& 3h^2d& 3hd^2& d^3&0\\
h^4& 4h^3d& 6h^2d^2& 4hd^3& d^4\\
\end{pmatrix}
\begin{pmatrix} 
1& 0& 0& 0&0\\
1& 2& 0& 0&0\\
1& 3& 3& 0&0\\
1& 4& 6& 4&0\\
1& 5& 10& 10&5\\
\end{pmatrix}^{-1} 
\begin{pmatrix} 
n\\
n^2\\
n^3\\
n^4\\
n^5
\end{pmatrix}</math>

Et dans le cas particulier <math>m=5,~ h=1,~ d=2 </math>, elle calcule la somme des <math>n</math> premiers nombres impairs consécutifs

En calculant la [[Matrice (mathématiques)|matrice]] T(h,d), dont les éléments suivent la [[formule du binôme de Newton]] avec les valeurs attribuées, c'est-à-dire T(1,2), et en trouvant la matrice inverse de la [[Matrice triangulaire|matrice triangulaire inférieure]] A obtenue à partir du [[triangle de Pascal]] privé du dernier élément de chaque ligne (matrice dont la dernière colonne est formée des [[Nombre de Bernoulli|nombres de Bernoulli]], indiqués en rouge), on a :

:<math>
T(1,2)=\begin{pmatrix} 
1& 0& 0& 0& 0\\
1& 2& 0& 0& 0 \\
1& 4& 4& 0& 0\\
1& 6& 12& 8& 0 \\
1& 8& 24& 32& 16 \\
\end{pmatrix},
\quad
A^{-1}=\begin{pmatrix}
\color{red}1 \color{black}&0 &0 &0 &0\\
\color{red}-\frac{1}{2}\color{black}&\frac{1}{2}&0 &0 &0  \\
\color{red}\frac{1}{6}\color{black}&-\frac{1}{2}&\frac{1}{3} &0 &0\\
\color{red}0\color{black}&\frac{1}{4}&-\frac{1}{2}&\frac{1}{4} &0\\
\color{red}-\frac{1}{30}\color{black}&0&\frac{1}{3}&-\frac{1}{2}&\frac{1}{5}
\end{pmatrix}
</math>

En multipliant les lignes par les colonnes des deux matrices, on obtient

: <math>\begin{pmatrix}
S_n^0({1,2})\\
S_n^1({1,2})\\
S_n^2({1,2})\\
S_n^3({1,2})\\
S_n^4({1,2})
\end{pmatrix}=
\begin{pmatrix}
1 &0 &0 &0 &0\\
0&1&0 &0 &0 \\
-\frac{1}{3}&0&\frac{4}{3} &0 &0 \\
0&-1&0&2 &0 \\
\frac{7}{15}&0&-\frac{8}{3}&0&\frac{16}{5}
\end{pmatrix}
\begin{pmatrix}
n\\
n^2\\
n^3\\
n^4\\
n^5\\
\end{pmatrix}=\begin{pmatrix}
n\\
n^2\\
-\frac{1}{3}n+\frac{4}{3}n^3\\
-n^2+2n^4\\
\frac{7}{15}n-\frac{8}{3}n^3+\frac{16}{5}n^5\\
\end{pmatrix}.</math>
et donc :

<math>S_n^0(1,2)=n
\quad S_n^1(1,2)=n^2
\quad S_n^2(1,2)=-\frac{1}{3}n+\frac{4}{3}n^3
\quad S_n^3(1,2)=-n^2+2n^4
\quad S_n^4(1,2)=\frac{7}{15}n-\frac{8}{3}n^3+\frac{16}{5}n^5
</math>.

Enfin, si l'on s'intéresse aux trois premières additions des sommes de puissances de nombres impairs, on a bien 
<nowiki>:</nowiki>

<math>S_3^0(1,2)=1^0+3^0+5^0=3,\quad  S_3^1(1,2)=1^1+3^1+5^1 =9=3^2 ,\quad S_3^2(1,2)=1^2+3^2+5^2=35=-1+36, </math>

<math>S_3^3(1,2)=1^3+3^3+5^3=153= -9+162,\quad S_3^4(1,2)=1^4+3^4+5^4=707=(21-1080+ 16\times 729)/15.  </math>

== Notes et références ==
{{Traduction/Référence|en|Faulhaber's formula|83158482|type=note}}
<References/>

== Voir aussi ==
=== Bibliographie ===
* {{en}} [[John Horton Conway]] et [[Richard Guy]], ''{{Langue|en|The Book of Numbers}}'', [[Springer Science+Business Media|Springer Verlag]], 1998 {{ISBN|0-387-97993-X}}, {{p.|107}}
* {{en}} [[Eric W. Weisstein]], ''{{Langue|en|CRC Concise Encyclopedia of Mathematics}}'', Chapman & Hall/CRC, 2003 {{ISBN|1-58488-347-2}}, {{p.|2331}}
* {{de}} Johann Faulhaber, ''[https://books.google.de/books?id=0pw_AAAAcAAJ {{Langue|la|Academia Algebrae}}]''. {{Langue|de|''Darinnen die miraculosische Inventiones zu den höchsten Cossen weiters ''continuirt'' und ''profitiert'' werden''}}, Augsburg, Johann Ulrich Schönig, 1631<!-- Call number QA154.8&nbsp;F3&nbsp;1631a&nbsp;f&nbsp;MATH at Stanford University Libraries.-->
=== Liens externes ===

* {{MathWorld|nom_url=FaulhabersFormula|titre=Faulhaber's Formula}}
* Maxime Bourrigan, [http://cm2.ens.fr/sites/default/files/summae_potestatum.pdf Sommes des puissances], sur Culture Math.

{{portail|théorie des nombres}}

[[Catégorie:Mathématiques discrètes]]