En mathématiques , la formule de Faulhaber , portant le nom du mathématicien allemand Johann Faulhaber, exprime la somme des puissances p -ième des n premiers entiers :
∑ k = 1 n k p = 1 p + 2 p + 3 p + ⋯ + n p ( pour n ∈ N et p ∈ N ) {\displaystyle \sum _{k=1}^{n}k^{p}=1^{p}+2^{p}+3^{p}+\cdots +n^{p}\qquad \left({\mbox{pour }}n\in \mathbb {N} {\text{ et }}p\in \mathbb {N} \right)} par une fonction polynomiale de degré p + 1 en n [ 1] , les coefficients impliquant les nombres de Bernoulli : B 2 = 1 6 , B 4 = − 1 30 , B 6 = 1 42 … {\displaystyle B_{2}={\tfrac {1}{6}},\quad B_{4}=-{\tfrac {1}{30}},\quad B_{6}={\tfrac {1}{42}}\ldots }
∑ k = 1 n k p = 1 p + 1 ( n p + 1 + 1 2 ( p + 1 ) n p + 1 6 ( p + 1 2 ) n p − 1 − 1 30 ( p + 1 4 ) n p − 3 + 1 42 ( p + 1 6 ) n p − 5 + … + ( p + 1 ) B p n ) {\displaystyle \sum _{k=1}^{n}k^{p}={\frac {1}{p+1}}\left(n^{p+1}+{\frac {1}{2}}(p+1){n^{p}}+{\frac {1}{6}}{p+1 \choose 2}{n^{p-1}}-{\frac {1}{30}}{p+1 \choose 4}{n^{p-3}}+{\frac {1}{42}}{p+1 \choose 6}{n^{p-5}}+\ldots +(p+1)B_{p}n\right)} .Les coefficients ( p + 1 j ) {\displaystyle \textstyle {p+1 \choose j}} qui apparaissent sont les coefficients binomiaux (aussi notés C p + 1 j {\displaystyle \mathrm {C} _{p+1}^{j}} ).
Dans la convention la plus usuelle, les nombres de Bernoulli sont B 0 = 1 , B 1 = − 1 2 , B 2 = 1 6 , B 3 = 0 , B 4 = − 1 30 … {\displaystyle B_{0}=1,\quad B_{1}=-{\tfrac {1}{2}},\quad B_{2}={\tfrac {1}{6}},\quad B_{3}=0,\quad B_{4}=-{\tfrac {1}{30}}\quad \dots } mais ici, une convention moins courante est adoptée, à savoir que le nombre B 1 {\displaystyle B_{1}} est changé en + 1 2 {\displaystyle +{\frac {1}{2}}} .
La formule de Faulhaber s'écrit (avec p ∈ N {\displaystyle p\in \mathbb {N} } et n ∈ N {\displaystyle n\in \mathbb {N} } ) :
∑ k = 1 n k p = 1 p + 1 ∑ j = 0 p ( p + 1 j ) B j n p + 1 − j {\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}} (avec B 1 = 1 2 {\displaystyle B_{1}={\tfrac {1}{2}}} au lieu de − 1 2 {\displaystyle -{\tfrac {1}{2}}} ).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. 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 n {\displaystyle n} 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 sommes multiples discrètes [Quoi ?] à une époque où l'analyse balbutie. Il utilise la k -symétrie, et donne aussi certaines généralisations remarquables[ 2] .
Exemples 1 0 + 2 0 + 3 0 + ⋯ + n 0 = n {\displaystyle 1^{0}+2^{0}+3^{0}+\cdots +n^{0}=n} 1 + 2 + 3 + ⋯ + n = n 2 + n 2 = n ( n + 1 ) 2 {\displaystyle 1+2+3+\cdots +n={n^{2}+n \over 2}={n(n+1) \over 2}} 1 2 + 2 2 + 3 2 + ⋯ + n 2 = 2 n 3 + 3 n 2 + n 6 = n ( n + 1 ) ( 2 n + 1 ) 6 {\displaystyle 1^{2}+2^{2}+3^{2}+\cdots +n^{2}={2n^{3}+3n^{2}+n \over 6}={n(n+1)(2n+1) \over 6}} 1 3 + 2 3 + 3 3 + ⋯ + n 3 = n 4 + 2 n 3 + n 2 4 = n 2 ( n + 1 ) 2 4 = ( 1 + 2 + 3 + ⋯ + n ) 2 {\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 ) 1 4 + 2 4 + 3 4 + ⋯ + n 4 = 6 n 5 + 15 n 4 + 10 n 3 − n 30 = n ( n + 1 ) ( 2 n + 1 ) ( 3 n 2 + 3 n − 1 ) 30 {\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}} 1 5 + 2 5 + 3 5 + ⋯ + n 5 = 2 n 6 + 6 n 5 + 5 n 4 − n 2 12 = n 2 ( n + 1 ) 2 ( 2 n 2 + 2 n − 1 ) 12 {\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}} 1 6 + 2 6 + 3 6 + ⋯ + n 6 = 6 n 7 + 21 n 6 + 21 n 5 − 7 n 3 + n 42 = n ( n + 1 ) ( 2 n + 1 ) ( 3 n 4 + 6 n 3 − 3 n + 1 ) 42 {\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 = −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] .
∑ k = 0 n − 1 k p = 1 p + 1 ∑ j = 0 p ( p + 1 j ) B j n p + 1 − j {\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 B 1 = − 1 2 {\displaystyle B_{1}=-{\tfrac {1}{2}}} ). La formule est valide pour tous entiers naturels p et n (y compris pour p = 0 , avec 00 = 1) :
0 0 + 1 0 + 2 0 + 3 0 + ⋯ + ( n − 1 ) 0 = n {\displaystyle 0^{0}+1^{0}+2^{0}+3^{0}+\cdots +(n-1)^{0}=n}
0 + 1 + 2 + 3 + ⋯ + ( n − 1 ) = n 2 − n 2 {\displaystyle 0+1+2+3+\cdots +(n-1)={n^{2}-n \over 2}}
0 + 1 + 2 2 + 3 2 + ⋯ + ( n − 1 ) 2 = 2 n 3 − 3 n 2 + n 6 {\displaystyle 0+1+2^{2}+3^{2}+\cdots +(n-1)^{2}={2n^{3}-3n^{2}+n \over 6}}
0 + 1 + 2 3 + 3 3 + ⋯ + ( n − 1 ) 3 = n 4 − 2 n 3 + n 2 4 {\displaystyle 0+1+2^{3}+3^{3}+\cdots +(n-1)^{3}={n^{4}-2n^{3}+n^{2} \over 4}}
0 + 1 + 2 4 + 3 4 + ⋯ + ( n − 1 ) 4 = 6 n 5 − 15 n 4 + 10 n 3 − n 30 {\displaystyle 0+1+2^{4}+3^{4}+\cdots +(n-1)^{4}={6n^{5}-15n^{4}+10n^{3}-n \over 30}}
0 + 1 + 2 5 + 3 5 + ⋯ + ( n − 1 ) 5 = 2 n 6 − 6 n 5 + 5 n 4 − n 2 12 {\displaystyle 0+1+2^{5}+3^{5}+\cdots +(n-1)^{5}={2n^{6}-6n^{5}+5n^{4}-n^{2} \over 12}}
Relation avec les polynômes de Bernoulli On peut écrire (pour p et n entiers naturels) :
S n p = ∑ k = 0 n k p = B p + 1 ( n + 1 ) − B p + 1 ( 0 ) p + 1 {\displaystyle S_{n}^{p}=\sum _{k=0}^{n}k^{p}={\frac {B_{p+1}(n+1)-B_{p+1}(0)}{p+1}}} ,où B p ( X ) {\displaystyle B_{p}(X)} est le polynôme de Bernoulli de rang p .
B 0 ( X ) = 1 {\displaystyle B_{0}(X)=1} B 1 ( X ) = X − 1 2 {\displaystyle B_{1}(X)=X-{\tfrac {1}{2}}} B 2 ( X ) = X 2 − X + 1 6 {\displaystyle B_{2}(X)=X^{2}-X+{\tfrac {1}{6}}} B 3 ( X ) = X 3 − 3 2 X 2 + 1 2 X {\displaystyle B_{3}(X)=X^{3}-{\tfrac {3}{2}}X^{2}+{\tfrac {1}{2}}X} On a B p ( 0 ) = B p {\displaystyle B_{p}(0)=B_{p}} , nombre de Bernoulli de rang p (avec B 1 ( 0 ) = − 1 2 {\displaystyle B_{1}(0)=-{\tfrac {1}{2}}} ).
Démonstration
Ceci provient du fait que :
B p + 1 ( X + 1 ) − B p + 1 ( X ) = ( p + 1 ) X p {\displaystyle B_{p+1}(X+1)-B_{p+1}(X)=(p+1)X^{p}} (1). En effet par télescopage :
A = ∑ k = 0 n ( B p + 1 ( k + 1 ) − B p + 1 ( k ) ) = B p + 1 ( n + 1 ) − B p + 1 ( 0 ) {\displaystyle A=\sum _{k=0}^{n}(B_{p+1}(k+1)-B_{p+1}(k))=B_{p+1}(n+1)-B_{p+1}(0)} , et par (1) :
A = ( p + 1 ) ∑ k = 0 n k p = ( p + 1 ) S n p {\displaystyle A=(p+1)\sum _{k=0}^{n}k^{p}=(p+1)S_{n}^{p}} , d'où la formule.
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
∑ k = 1 n k p = 1 p + 1 ∑ j = 0 p ( p + 1 j ) B j n p + 1 − j = 1 p + 1 ∑ j = 0 p ( p + 1 j ) B j n p + 1 − j = ( B + n ) p + 1 − B p + 1 p + 1 {\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
T ( b j ) = B j {\displaystyle T(b^{j})=B_{j}} . On peut alors écrire
∑ k = 1 n k p = 1 p + 1 ∑ j = 0 p ( p + 1 j ) B j n p + 1 − j = 1 p + 1 ∑ j = 0 p ( p + 1 j ) T ( b j ) n p + 1 − j {\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}} = 1 p + 1 T ( ∑ j = 0 p ( p + 1 j ) b j n p + 1 − j ) = T ( ( b + n ) p + 1 − b p + 1 p + 1 ) . {\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).}
Polynômes de Faulhaber Faulhaber a observé (sans en donner de preuve) que
si p est impair, alors 1 p + 2 p + 3 p + ⋯ + n p {\displaystyle 1^{p}+2^{p}+3^{p}+\cdots +n^{p}} est une fonction polynomiale de y = 1 + 2 + 3 + ⋯ + n = n 2 + n 2 {\displaystyle y=1+2+3+\cdots +n={n^{2}+n \over 2}} , si p est pair, alors 1 p + 2 p + 3 p + ⋯ + n p {\displaystyle 1^{p}+2^{p}+3^{p}+\cdots +n^{p}} est le produit de 2 n + 1 {\displaystyle 2n+1} par une fonction polynomiale de y . Ces propriétés se montrent en utilisant respectivement les relations de récurrence forte sur les sommes de degré impair et les relations de récurrence forte sur les sommes de degré pair .
Ainsi, pour p impair :
1 3 + 2 3 + 3 3 + ⋯ + n 3 = y 2 {\displaystyle 1^{3}+2^{3}+3^{3}+\cdots +n^{3}=y^{2}} 1 5 + 2 5 + 3 5 + ⋯ + n 5 = 4 y 3 − y 2 3 {\displaystyle 1^{5}+2^{5}+3^{5}+\cdots +n^{5}={4y^{3}-y^{2} \over 3}} 1 7 + 2 7 + 3 7 + ⋯ + n 7 = 6 y 4 − 4 y 3 + y 2 3 {\displaystyle 1^{7}+2^{7}+3^{7}+\cdots +n^{7}={6y^{4}-4y^{3}+y^{2} \over 3}} (et donc 1 5 + 2 5 + 3 5 + ⋯ + n 5 + 1 7 + 2 7 + 3 7 + ⋯ + n 7 = 2 y 4 {\displaystyle 1^{5}+2^{5}+3^{5}+\cdots +n^{5}+1^{7}+2^{7}+3^{7}+\cdots +n^{7}=2y^{4}} ) 1 9 + 2 9 + 3 9 + ⋯ + n 9 = 16 y 5 − 20 y 4 + 12 y 3 − 3 y 2 5 {\displaystyle 1^{9}+2^{9}+3^{9}+\cdots +n^{9}={16y^{5}-20y^{4}+12y^{3}-3y^{2} \over 5}} 1 11 + 2 11 + 3 11 + ⋯ + n 11 = 16 y 6 − 32 y 5 + 34 y 4 − 20 y 3 + 5 y 2 3 {\displaystyle 1^{11}+2^{11}+3^{11}+\cdots +n^{11}={16y^{6}-32y^{5}+34y^{4}-20y^{3}+5y^{2} \over 3}} et pour p pair :
1 2 + 2 2 + 3 2 + ⋯ + n 2 = ( 2 n + 1 ) y 3 {\displaystyle 1^{2}+2^{2}+3^{2}+\cdots +n^{2}=(2n+1){\frac {y}{3}}} 1 4 + 2 4 + 3 4 + ⋯ + n 4 = ( 2 n + 1 ) 6 y 2 − y 15 {\displaystyle 1^{4}+2^{4}+3^{4}+\cdots +n^{4}=(2n+1){\frac {6y^{2}-y}{15}}} 1 6 + 2 6 + 3 6 + ⋯ + n 6 = ( 2 n + 1 ) 12 y 3 − 6 y 2 + y 15 {\displaystyle 1^{6}+2^{6}+3^{6}+\cdots +n^{6}=(2n+1){\frac {12y^{3}-6y^{2}+y}{15}}} 1 8 + 2 8 + 3 8 + ⋯ + n 8 = ( 2 n + 1 ) 40 y 4 − 40 y 3 + 18 y 2 − 3 y 45 {\displaystyle 1^{8}+2^{8}+3^{8}+\cdots +n^{8}=(2n+1){\frac {40y^{4}-40y^{3}+18y^{2}-3y}{45}}} Quelques auteurs[ 4] appellent ces polynômes P ( y ) {\displaystyle P(y)} , avec y = n ( n + 1 ) 2 {\displaystyle y={\frac {n(n+1)}{2}}} , « 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[ 2] .
Expression utilisant les nombres de Stirling de seconde espèce Pour tout p ⩾ 1 {\displaystyle p\geqslant 1} , on a la relation :
∑ k = 0 n k p = ∑ i = 1 p S ( p , i ) i + 1 ( n + 1 ) i + 1 {\displaystyle \sum _{k=0}^{n}k^{p}=\sum _{i=1}^{p}{\frac {S(p,i)}{i+1}}(n+1)_{i+1}} où les S ( p , i ) {\displaystyle S(p,i)} sont les nombres de Stirling de seconde espèce (nombre de partitions en i parties d'un ensemble à p éléments) et ( n + 1 ) i + 1 = ( n + 1 ) ( n ) . . . ( n + 1 − i ) {\displaystyle (n+1)_{i+1}=(n+1)(n)...(n+1-i)} (symbole de Pochhammer ).
Par exemple ∑ k = 0 n k = 1 2 ( n + 1 ) n {\displaystyle \sum _{k=0}^{n}k={\frac {1}{2}}(n+1)n} , et ∑ k = 0 n k 2 = 1 2 ( n + 1 ) n + 1 3 ( n + 1 ) n ( n − 1 ) {\displaystyle \sum _{k=0}^{n}k^{2}={\frac {1}{2}}(n+1)n+{\frac {1}{3}}(n+1)n(n-1)} .
Relations de récurrence liant ces sommes
Relation de récurrence forte (Pascal, 1655) Les sommes S n p = ∑ k = 0 n k p {\displaystyle S_{n}^{p}=\sum _{k=0}^{n}k^{p}} peuvent se calculer de proche en proche grâce à la relation[ 5] :
( p + 1 ) S n p = ( n + 1 ) p + 1 − ∑ q = 0 p − 1 ( p + 1 q ) S n q {\displaystyle (p+1)S_{n}^{p}=(n+1)^{p+1}-\sum _{q=0}^{p-1}{\binom {p+1}{q}}S_{n}^{q}} . Démonstration
Par télescopage :
∑ k = 0 n ( ( k + 1 ) p + 1 − k p + 1 ) = ( n + 1 ) p + 1 {\displaystyle \sum _{k=0}^{n}((k+1)^{p+1}-k^{p+1})=(n+1)^{p+1}} et par la formule du binôme :
∑ k = 0 n ( ( k + 1 ) p + 1 − k p + 1 ) = ∑ k = 0 n ∑ q = 0 p ( p + 1 q ) k q = ∑ q = 0 p ( p + 1 q ) ∑ k = 0 n k q = ( p + 1 ) S n p + ∑ q = 0 p − 1 ( p + 1 q ) S n q {\displaystyle \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}} d'où la formule annoncée.
Par exemple, on a S n 0 = 0 0 + 1 0 + 2 0 + 3 0 + ⋯ + n 0 = n + 1 {\displaystyle S_{n}^{0}=0^{0}+1^{0}+2^{0}+3^{0}+\cdots +n^{0}=n+1} ;
donc, 2 S n 1 = ( n + 1 ) 2 − ( n + 1 ) = n ( n + 1 ) {\displaystyle 2S_{n}^{1}=(n+1)^{2}-(n+1)=n(n+1)} ,
puis 3 S n 2 = ( n + 1 ) 3 − ( n + 1 ) − 3 n ( n + 1 ) 2 = n + 1 2 ( 2 n 2 + 4 n + 2 − 2 − 3 n ) = n ( n + 1 ) ( 2 n + 1 ) 2 {\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.
Relation de récurrence forte sur les sommes de degré impair Elle s'écrit :
2 ( p + 1 ) S n 2 p + 1 = ( n ( n + 1 ) ) p + 1 − 2 ∑ 1 ⩽ q ⩽ p / 2 ( p + 1 2 q + 1 ) S n 2 p + 1 − 2 q {\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}} . Démonstration
La démonstration est similaire à la précédente. On procède par télescopage :
A n = ∑ k = 1 n ( ( k ( k + 1 ) ) p + 1 − ( k ( k − 1 ) ) p + 1 ) = ( n ( n + 1 ) ) p + 1 {\displaystyle A_{n}=\sum _{k=1}^{n}((k(k+1))^{p+1}-(k(k-1))^{p+1})=(n(n+1))^{p+1}} , et par la formule du binôme :
A n = ∑ k = 1 n k p + 1 ∑ q = 0 p + 1 ( p + 1 q ) ( 1 − ( − 1 ) q ) k p + 1 − q = ∑ k = 1 n k p + 1 ∑ 0 ⩽ 2 q + 1 ⩽ p + 1 ( p + 1 2 q + 1 ) 2 k p + 1 − 2 q − 1 {\displaystyle 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}} donc :
A n = ∑ 0 ⩽ 2 q + 1 ⩽ p + 1 ∑ k = 1 n ( p + 1 2 q + 1 ) 2 k 2 p + 1 − 2 q = ∑ 0 ⩽ q ⩽ p / 2 ( p + 1 2 q + 1 ) 2 S n 2 p + 1 − 2 q = 2 ( p + 1 ) S n 2 p + 1 + 2 ∑ 1 ⩽ q ⩽ p / 2 ( p + 1 2 q + 1 ) S n 2 p + 1 − 2 q {\displaystyle 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}} d'où la formule annoncée.
En faisant p = 1 {\displaystyle p=1} , on obtient par exemple directement que 4 S n 3 = ( n ( n + 1 ) ) 2 {\displaystyle 4S_{n}^{3}=(n(n+1))^{2}} .
Cette relation permet également de montrer par récurrence que S n 2 p + 1 {\displaystyle S_{n}^{2p+1}} est un polynôme de degré p + 1 {\displaystyle p+1} en n ( n + 1 ) {\displaystyle n(n+1)} .
Relation de récurrence forte sur les sommes de degré pair Elle s'écrit, pour p strictement positif :
( 4 p + 2 ) S n 2 p = n p ( n + 1 ) p ( 2 n + 1 ) − ∑ 1 ⩽ q ⩽ p / 2 ( 4 ( p 2 q + 1 ) + 2 ( p 2 q ) ) S n 2 p − 2 q {\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}} . Démonstration
La démonstration est similaire à la précédente. On procède par télescopage :
A n = ∑ k = 1 n ( k p ( k + 1 ) p ( 2 k + 1 ) − ( k − 1 ) p k p ( 2 k − 1 ) ) = n p ( n + 1 ) p ( 2 n + 1 ) {\displaystyle A_{n}=\sum _{k=1}^{n}(k^{p}(k+1)^{p}(2k+1)-(k-1)^{p}k^{p}(2k-1))=n^{p}(n+1)^{p}(2n+1)} , et par la formule du binôme :
A n = ∑ k = 1 n k p ∑ q = 0 p ( p q ) ( k p − q ( 2 k + 1 ) − ( − 1 ) q k p − q ( 2 k − 1 ) ) = ∑ k = 1 n k p ( ∑ q i m p a i r ( p q ) 4 k p − q + 1 + ∑ q p a i r ( p q ) 2 k p − q ) {\displaystyle A_{n}=\sum _{k=1}^{n}k^{p}\sum _{q=0}^{p}{\binom {p}{q}}(k^{p-q}(2k+1)-(-1)^{q}k^{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)} donc
A n = ∑ k = 1 n k p ( ∑ q p a i r ( p q + 1 ) 4 k p − q + ∑ q p a i r ( p q ) 2 k p − q ) {\displaystyle 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)} donc :
A n = ∑ 0 ⩽ q ⩽ p / 2 ∑ k = 1 n ( 4 ( p 2 q + 1 ) + 2 ( p 2 q ) ) k 2 p − 2 q = ∑ 0 ⩽ q ⩽ p / 2 ( 4 ( p 2 q + 1 ) + 2 ( p 2 q ) ) S n 2 p − 2 q {\displaystyle 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}} d'où la formule annoncée.
En faisant p = 1 {\displaystyle p=1} , on obtient par exemple directement que 6 S n 2 = n ( n + 1 ) ( 2 n + 1 ) {\displaystyle 6S_{n}^{2}=n(n+1)(2n+1)} .
Cette relation permet également de montrer par récurrence que S n 2 p {\displaystyle S_{n}^{2p}} est le produit de ( 2 n + 1 ) {\displaystyle (2n+1)} par un polynôme de degré p en n ( n + 1 ) {\displaystyle n(n+1)} .
Pour les sommes quelconques La relation de récurrence forte vue plus haut peut s'écrire :
∑ q = 0 p ( p + 1 q ) S n q = ( n + 1 ) p + 1 {\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 S n 0 , S n 1 , ⋯ , S n q {\displaystyle S_{n}^{0},S_{n}^{1},\cdots ,S_{n}^{q}} .
Si A q + 1 {\displaystyle A_{q+1}} est la matrice carrée triangulaire inférieure d'ordre q +1 définie par A q + 1 ( i , j ) = ( i + 1 j ) {\displaystyle A_{q+1}(i,j)={\binom {i+1}{j}}} (les indices variant de 0 à q ), le système s'écrit[ 4] :
A q + 1 ( S n 0 S n 1 ⋯ S n q ) = ( n + 1 ( n + 1 ) 2 ⋯ ( n + 1 ) q + 1 ) {\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 :
( S n 0 S n 1 ⋯ S n q ) = A q + 1 − 1 ( n + 1 ( n + 1 ) 2 ⋯ ( n + 1 ) q + 1 ) {\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, A 7 = ( 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 ) {\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 A 7 − 1 = ( 1 0 0 0 0 0 0 − 1 2 1 2 0 0 0 0 0 1 6 − 1 2 1 3 0 0 0 0 0 1 4 − 1 2 1 4 0 0 0 − 1 30 0 1 3 − 1 2 1 5 0 0 0 − 1 12 0 5 12 − 1 2 1 6 0 1 42 0 − 1 6 0 1 2 − 1 2 1 7 ) {\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 S n 0 = n + 1 {\displaystyle S_{n}^{0}=n+1} , S n 1 = ( n + 1 ) n 2 {\displaystyle S_{n}^{1}={\frac {(n+1)n}{2}}} , etc.
La matrice A q + 1 {\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 .
Pour les sommes à exposants impairs La relation ci-dessus sur les sommes à exposants impairs peut aussi s'écrire :
∑ ( i + 1 ) / 2 ⩽ j ⩽ i 2 ( i 2 j − i − 1 ) S n 2 j − 1 = ( n ( n + 1 ) ) i {\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 S n 1 , S n 3 , ⋯ , S n 2 p − 1 {\displaystyle S_{n}^{1},S_{n}^{3},\cdots ,S_{n}^{2p-1}} .
Si B p {\displaystyle B_{p}} est la matrice carrée triangulaire inférieure d'ordre p définie par B p ( i , j ) = 2 ( i 2 j − i − 1 ) {\displaystyle B_{p}(i,j)=2{\binom {i}{2j-i-1}}} , le système s'écrit
B p ( S n 1 S n 3 ⋯ S n 2 p − 1 ) = ( n ( n + 1 ) n 2 ( n + 1 ) 2 ⋯ n p ( n + 1 ) p ) {\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 ( S n 1 S n 3 ⋯ S n 2 p − 1 ) = B p − 1 ( n ( n + 1 ) n 2 ( n + 1 ) 2 ⋯ n p ( n + 1 ) p ) {\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, B 4 = 2 ( 1 0 0 0 0 2 0 0 0 1 3 0 0 0 4 4 ) {\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 B 4 − 1 = ( 1 2 0 0 0 0 1 4 0 0 0 − 1 12 1 6 0 0 1 12 − 1 6 1 8 ) {\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 S n 1 = n ( n + 1 ) / 2 {\displaystyle S_{n}^{1}=n(n+1)/2} , S n 3 = n 2 ( n + 1 ) 2 4 {\displaystyle S_{n}^{3}={\frac {n^{2}(n+1)^{2}}{4}}} , S n 5 = n 3 ( n + 1 ) 3 6 − n 2 ( n + 1 ) 2 12 {\displaystyle S_{n}^{5}={{n^{3}(n+1)^{3}} \over 6}-{\frac {n^{2}(n+1)^{2}}{12}}} etc.
La matrice B p {\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.
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.
Sommes multiples de produits de puissances distinctes Pour tous m {\displaystyle m} , q {\displaystyle q} , n {\displaystyle n} , p ∈ N {\displaystyle p\in \mathbb {N} } tels que n ⩾ q + m − 1 , m ⩾ 1 {\displaystyle n\geqslant q+m-1,m\geqslant 1} , la somme multiple de puissances p {\displaystyle p} distinctes, d'ordre m {\displaystyle m} et de bornes q {\displaystyle q} et n {\displaystyle n} , est définie par
σ m ( q p , ⋯ , n p ) = ∑ q ⩽ k 1 < ⋯ < k m ⩽ n k m p ⋯ k 1 p , {\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 ( n − q + 1 m ) {\displaystyle {\binom {n-q+1}{m}}} produits de m {\displaystyle m} entiers distincts entre q {\displaystyle q} et n {\displaystyle n} élevés à la même puissance p {\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] .
L’application de la formule de Faulhaber pour des sommes simples de puissances conduit à la formule de Faulhaber généralisée suivante[ 6] .
Exemples ∑ 1 ⩽ k 1 < k 2 ⩽ n k 2 k 1 = n ( n − 1 ) ( n + 1 ) ( 3 n + 2 ) 24 = ( n + 1 3 ) 3 n + 2 4 , {\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 ∑ 1 ⩽ k 1 < k 2 ⩽ n k 2 2 k 1 2 = n ( n − 1 ) ( n + 1 ) ( 2 n − 1 ) ( 2 n + 1 ) ( 5 n + 6 ) 360 = ( 2 n + 2 5 ) 5 n + 6 4 ! , {\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 ∑ 1 ⩽ k 1 < k 2 < k 3 ⩽ n k 3 2 k 2 2 k 1 2 = ( 2 n + 2 7 ) 35 n 2 + 91 n + 60 144 , {\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, ∑ 1 ⩽ k 1 < ⋯ < k m ⩽ n k m ⋯ k 1 = ( − 1 ) m s ( n + 1 , n + 1 − m ) {\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ù s ( . , . ) {\displaystyle s(.,.)} représente un nombre de Stirling de première espèce .
Sommes multiples de produits de puissances avec répétitions possibles Pour tout m {\displaystyle m} , q {\displaystyle q} , n {\displaystyle n} , p ∈ N {\displaystyle p\in \mathbb {N} } , cette somme de puissances p {\displaystyle p} d'ordre m {\displaystyle m} avec des bornes q {\displaystyle q} et n {\displaystyle n} est définie par
∑ q ⩽ k 1 ⩽ ⋯ ⩽ k m ⩽ n k m p ⋯ k 1 p = ∑ k m = q n ∑ k m − 1 = q k m ⋯ ∑ k 1 = q k 2 k m p ⋯ k 1 p {\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 ( ( n − q + 1 m ) ) {\displaystyle \left({\binom {n-q+1}{m}}\right)} produits de m {\displaystyle m} entiers entre q {\displaystyle q} et n {\displaystyle n} , avec répétitions possibles , élevés à la puissance p {\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 [ 7] .
Une conséquence directe de ce théorème est la formule de Faulhaber généralisée suivante [ 7] .
Exemples ∑ 1 ⩽ k 1 ⩽ k 2 ⩽ n k 2 k 1 = n ( n + 1 ) ( n + 2 ) ( 3 n + 1 ) 24 = ( n + 2 3 ) 3 n + 1 4 , {\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 . ∑ 1 ⩽ k 1 ⩽ k 2 ⩽ n k 2 2 k 1 2 = n ( n + 1 ) ( n + 2 ) ( 2 n + 1 ) ( 2 n + 3 ) ( 5 n − 1 ) 360 = ( 2 n + 4 5 ) 5 n − 1 4 ! , {\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 . ∑ 1 ⩽ k 1 ⩽ k 2 ⩽ k 3 ⩽ n k 3 2 k 2 2 k 1 2 = ( 2 n + 6 7 ) 35 n 2 − 21 n + 4 144 , {\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 . Notons que pour p = 1, ∑ 1 ⩽ k 1 ⩽ ⋯ ⩽ k m ⩽ n k m ⋯ k 1 = S ( n + m , n ) {\displaystyle \sum _{1\leqslant k_{1}\leqslant \cdots \leqslant k_{m}\leqslant n}k_{m}\cdots k_{1}=S(n+m,n)} , où S ( . , . ) {\displaystyle S(.,.)} désigne un nombre de Stirling de seconde espèce .
Notes et références (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé
« Faulhaber's formula » (voir la liste des auteurs) .
↑ Nulle en n = 0 (cf. « Somme vide ») donc produit de n par une fonction polynomiale de degré p . ↑ a et b (en) Donald E. Knuth , « Johann Faulhaber and sums of powers », Math. Comp. , vol. 61, 1993 , p. 277-294 (lire en ligne) . ↑ Ceci vient de ce que ∑ k = 1 n − 1 k p = ∑ k = 1 n k p − n p {\displaystyle \sum _{k=1}^{n-1}k^{p}=\sum _{k=1}^{n}k^{p}-n^{p}} , ce qui change n p 2 {\displaystyle {\frac {n^{p}}{2}}} en − n p 2 {\displaystyle -{\frac {n^{p}}{2}}} . ↑ a et b (en) A. W. F. Edwards, « Sums of powers of integers: a little of the history », Math. Gazette , no 66, 1982 , p. 22-28 ↑ (la) Blaise Pascal, Potestatum Numericarum Summa , 1665 ↑ a et b (en) Roudy El Haddad, « A generalization of multiple zeta values. Part 2: Multiple sums », Notes on Number Theory and Discrete Mathematics (DOI 10.7546/nntdm.2022.28.2.200-233 ) ↑ a et b (en) Roudy El Haddad, « A generalization of multiple zeta values. Part 1: Recurrent sums », Notes on Number Theory and Discrete Mathematics (DOI 10.7546/nntdm.2022.28.2.167-199 )
Voir aussi
Bibliographie (en) John Horton Conway et Richard Guy , The Book of Numbers , Springer Verlag , 1998 (ISBN 0-387-97993-X ) , p. 107 (en) Eric Weisstein , CRC Concise Encyclopedia of Mathematics , Chapman & Hall/CRC, 2003 (ISBN 1-58488-347-2 ) , p. 2331 (de) Johann Faulhaber, Academia Algebrae . Darinnen die miraculosische Inventiones zu den höchsten Cossen weiters continuirt und profitiert werden , Augsburg, Johann Ulrich Schönig, 1631
Lien externe (en) Eric W. Weisstein , « Faulhaber's Formula », sur MathWorld
Arithmétique et théorie des nombres