Faulhaber formula

The Faulhaber's formula , named after Johannes Faulhaber of DE Knuth describes how the sum of the first -th powers with a polynomial in the degree of charge can. ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle P_{k+1}(n)}$ ${\displaystyle n}$ ${\displaystyle k+1}$

${\displaystyle \sum _{h=1}^{n}h^{k}=1^{k}+2^{k}+3^{k}+\cdots +n^{k}=P_{k+1}(n)\qquad (k,n\in \mathbb {N} _{0})}$

The coefficients of the polynomial can be calculated with the help of Bernoulli numbers . ${\displaystyle P_{k+1}(n)}$

Representation of the polynomial using the Bernoulli numbers

The Bernoulli numbers are required to calculate the coefficients of this polynomial . In the following, denote the -th Bernoulli number of the first kind and the Bernoulli numbers of the second kind, then Faulhaber's formula looks like this: ${\displaystyle B_{j}}$ ${\displaystyle j}$ ${\displaystyle {\overline {B}}_{j}}$

${\displaystyle {\begin{aligned}\sum _{h=1}^{n}h^{k}&={\frac {1}{k+1}}\sum _{j=0}^{k}(-1)^{j}{k+1 \choose j}B_{j}n^{k+1-j}={\frac {1}{k+1}}\sum _{j=0}^{k}{k+1 \choose j}{\overline {B}}_{j}n^{k+1-j}\\&={\frac {n^{k}}{2}}+{\frac {1}{k+1}}\sum _{i=0}^{\lfloor k/2\rfloor }{k+1 \choose 2i}B_{2i}n^{k+1-2i}\end{aligned}}}$

If, instead of the first, only the first potencies are considered, then Faulhaber's formula can also be described and obtained for “without exception” ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle B_{1}}$

${\displaystyle \sum _{h=0}^{n-1}h^{k}={\frac {1}{k+1}}\sum _{j=0}^{k}{k+1 \choose j}B_{j}n^{k+1-j}}$

Explicit representations

${\displaystyle {\begin{array}{lllr}1^{0}+2^{0}+3^{0}+\cdots +n^{0}&=n\\1^{1}+2^{1}+3^{1}+\cdots +n^{1}&={\tfrac {1}{2}}n^{2}+{\tfrac {1}{2}}n\qquad {\text{(Gaußsche Summenformel)}}\\1^{2}+2^{2}+3^{2}+\cdots +n^{2}&={\tfrac {1}{3}}n^{3}+{\tfrac {1}{2}}n^{2}+{\tfrac {1}{6}}n\qquad {\text{(Quadratische Pyramidalzahl)}}\\1^{3}+2^{3}+3^{3}+\cdots +n^{3}&={\tfrac {1}{4}}n^{4}+{\tfrac {1}{2}}n^{3}+{\tfrac {1}{4}}n^{2}\qquad {\text{(Quadrat der Summe der ersten n Zahlen)}}\\1^{4}+2^{4}+3^{4}+\cdots +n^{4}&={\tfrac {1}{5}}n^{5}+{\tfrac {1}{2}}n^{4}+{\tfrac {1}{3}}n^{3}-{\tfrac {1}{30}}n\\1^{5}+2^{5}+3^{5}+\cdots +n^{5}&={\tfrac {1}{6}}n^{6}+{\tfrac {1}{2}}n^{5}+{\tfrac {5}{12}}n^{4}-{\tfrac {1}{12}}n^{2}\\1^{6}+2^{6}+3^{6}+\cdots +n^{6}&={\tfrac {1}{7}}n^{7}+{\tfrac {1}{2}}n^{6}+{\tfrac {1}{2}}n^{5}-{\tfrac {1}{6}}n^{3}+{\tfrac {1}{42}}n\\1^{7}+2^{7}+3^{7}+\cdots +n^{7}&={\tfrac {1}{8}}n^{8}+{\tfrac {1}{2}}n^{7}+{\tfrac {7}{12}}n^{6}-{\tfrac {7}{24}}n^{4}+{\tfrac {1}{12}}n^{2}\\1^{8}+2^{8}+3^{8}+\cdots +n^{8}&={\tfrac {1}{9}}n^{9}+{\tfrac {1}{2}}n^{8}+{\tfrac {2}{3}}n^{7}-{\tfrac {7}{15}}n^{5}+{\tfrac {2}{9}}n^{3}-{\tfrac {1}{30}}n\\1^{9}+2^{9}+3^{9}+\cdots +n^{9}&={\tfrac {1}{10}}n^{10}+{\tfrac {1}{2}}n^{9}+{\tfrac {3}{4}}n^{8}-{\tfrac {7}{10}}n^{6}+{\tfrac {1}{2}}n^{4}-{\tfrac {3}{20}}n^{2}\\1^{10}+2^{10}+3^{10}+\cdots +n^{10}&={\tfrac {1}{11}}n^{11}+{\tfrac {1}{2}}n^{10}+{\tfrac {5}{6}}n^{9}-n^{7}+n^{5}-{\tfrac {1}{2}}n^{3}+{\tfrac {5}{66}}n\\1^{11}+2^{11}+3^{11}+\cdots +n^{11}&={\tfrac {1}{12}}n^{12}+{\tfrac {1}{2}}n^{11}+{\tfrac {11}{12}}n^{10}-{\tfrac {11}{8}}n^{8}+{\tfrac {11}{6}}n^{6}-{\tfrac {11}{8}}n^{4}+{\tfrac {5}{12}}n^{2}\\1^{12}+2^{12}+3^{12}+\cdots +n^{12}&={\tfrac {1}{13}}n^{13}+{\tfrac {1}{2}}n^{12}+n^{11}-{\tfrac {11}{6}}n^{9}+{\tfrac {22}{7}}n^{7}-{\tfrac {33}{10}}n^{5}+{\tfrac {5}{3}}n^{3}-{\tfrac {691}{2730}}n\\\end{array}}}$

The low coefficients in original fractions, as we know them for small ones from school mathematics, are not at all typical for the further course. Already in its first appearance a coefficient> 1 on; at even higher potencies this becomes the rule. The reason for this is the Bernoulli numbers , which increase sharply after a series of low values, even more than any exponential function, and approach infinity. They themselves form the coefficients of the linear terms, and since they become zero for uneven exponents other than 1, these terms are accordingly missing in the sum formulas. ${\displaystyle k}$ ${\displaystyle k=11}$

In general:

${\displaystyle 1^{k}+2^{k}+3^{k}+\dotsb +n^{k}={\tfrac {1}{k+1}}n^{k+1}+{\tfrac {1}{2}}n^{k}+{\mathcal {O}}(n^{k-1})}$

(This denotes the O notation .) Here you can also see the connection with Cavalieri's integral formula; a sum of powers is a power with a degree higher by 1. This also applies to the trivial special case of , because the integral of a constant function is a linear one. ${\displaystyle {\mathcal {O}}}$ ${\displaystyle k=0}$

When expanding from to , one first obtains the divergent harmonic series for , but convergent power sums for all . By definition, their limit values ​​are the function values ​​of the Riemann zeta function . ${\displaystyle k}$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle k=-1}$ ${\displaystyle k\leq -2}$

All of these are special cases of the general Euler-Maclaurin formula applied to the function with any real exponent . ${\displaystyle x^{k}}$ ${\displaystyle k}$

Relationship with Bernoulli polynomials

The sum of the first -th powers can also be expressed with the help of Bernoulli polynomials : ${\displaystyle n}$ ${\displaystyle k}$

${\displaystyle \sum _{h=0}^{n}h^{k}={\frac {{\text{B}}_{k+1}(n+1)-{\text{B}}_{k+1}(0)}{k+1}},}$

The -th denotes Bernoulli's polynomial. ${\displaystyle {\text{B}}_{j}}$ ${\displaystyle j}$

Faulhaber polynomials

The sums of odd powers

${\displaystyle \sum _{h=1}^{n}h^{2k+1}=1^{2k+1}+2^{2k+1}+3^{2k+1}+\cdots +n^{2k+1}\qquad (k,n\in \mathbb {N} _{0})}$

can also be represented as a polynomial in . Such polynomials in instead of in are also called Faulhaber polynomials . Johannes Faulhaber himself only knew the formula in the form described below, and only calculated the odd cases as a polynomial in and assumed that a corresponding polynomial existed for all odd numbers , but without giving a proof for it. He was not familiar with the concept of Bernoulli numbers. ${\displaystyle m=1+2+\dotsb +n={\tfrac {1}{2}}n(n+1)}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle k=1,3,5,\dotsc ,17}$ ${\displaystyle m}$ ${\displaystyle k}$

Some examples of small exponents:

${\displaystyle 1^{3}+2^{3}+3^{3}+\cdots +n^{3}=m^{2}}$     (Follow A000537 in OEIS )

${\displaystyle 1^{5}+2^{5}+3^{5}+\cdots +n^{5}={\frac {4m^{3}-m^{2}}{3}}}$     (Follow A000539 in OEIS )

${\displaystyle 1^{7}+2^{7}+3^{7}+\cdots +n^{7}={\frac {6m^{4}-4m^{3}+m^{2}}{3}}}$     (Follow A000541 in OEIS )

${\displaystyle 1^{9}+2^{9}+3^{9}+\cdots +n^{9}={\frac {16m^{5}-20m^{4}+12m^{3}-3m^{2}}{5}}}$     (Follow A007487 in OEIS )

${\displaystyle 1^{11}+2^{11}+3^{11}+\cdots +n^{11}={\frac {16m^{6}-32m^{5}+34m^{4}-20m^{3}+5m^{2}}{3}}}$     (Follow A123095 in OEIS )

Generally applies to everyone : ${\displaystyle k\in \mathbb {N} }$

${\displaystyle 1^{2k-1}+2^{2k-1}+3^{2k-1}+\cdots +n^{2k-1}={\frac {1}{2^{2k}(2k)}}\sum _{h=0}^{k-1}B_{2h}{\binom {2k}{2h}}(2-2^{2h})\left((8m+1)^{k-h}-1\right)}$

which represents a polynomial of degree in or explicitly as a polynomial in ${\displaystyle k}$ ${\displaystyle 8m+1}$ ${\displaystyle m}$

${\displaystyle \sum _{h=1}^{n}h^{2k-1}={\frac {1}{2k}}\sum _{i=1}^{k}a_{i,k}\,m^{i}\qquad {\text{mit}}\quad a_{i,k}=(-2)^{i}\sum _{j=0}^{i}{2k \choose i-j}{i+j \choose j}{\frac {i-j}{i+j}}B_{2k-i+j}}$

Historical

Faulhaber himself did not know the formula in its current general form, and the Bernoulli numbers were not yet known in his time. However, he knew at least the first 17 cases and the constructions of the polynomials named after him. In 1834 Carl Gustav Jacob Jacobi published the first known proof of Faulhaber's formula using the Euler-Maclaurin formula . Further evidence was published by L. Tits in 1923 and by AWF Edwards in 1986. Donald Ervin Knuth examined generalizations, represented the sums as polynomials in with fixed , and contributed to the popularization of Faulhaber's polynomials. ${\displaystyle n(n+1)\cdots (n+r)}$ ${\displaystyle r}$

literature

• Donald E. Knuth : Johann Faulhaber and Sums of Powers. Math. Comp. 61 (1993), no. 203, pp. 277-294. arxiv : math / 9207222 .
• John H. Conway , Richard Guy : The Book of Numbers. Copernicus (Springer), New York 1996, ISBN 0-387-97993-X , p. 106, ( excerpt (Google) ).
• Johann Faulhaber : Academia Algebrae. Therein the Miraculous Inventiones to be continued and profited to the highest Cosses. The same thing was prophesied to scholars at all universities in the whole of Europe fifteen years ago, then continued, also dedicated to all mathematicians in the whole wide world, but bithero, never so high, bit on the regulated censorship, was published by an open truck. Which precedes a brief reflection, which one should use for authors according to order, who wants to teach and seize the Coß fruitfully, soon, also fundamentally. Augsburg: Johann Ulrich Schönig, 1631. ( online copy (Google) )

Web links

• Eric W. Weisstein : Faulhaber's formula . In: MathWorld (English).
• John J. O'Connor, Edmund F. Robertson :  Johann Faulhaber. In: MacTutor History of Mathematics archive .
• Helmut Richter, Bernhard Schiekel: Power sums, Bernoulli numbers and Euler's empirical formula. doi: 10.18725 / OPARU-1819
• Tobias Krähling: propositional logic. (PDF; 148 kB) - Derivation of the power sum formula / the polynomial

Individual evidence

1. ^ ^{A b} Donald E. Knuth : Johann Faulhaber and Sums of Powers . Math. Comp. 61 (1993), no. 203, pp. 277-294. arxiv : math / 9207222 .
2. ^ Carl Gustav Jacob Jacobi: De usu legitimo formulae summatoriae Maclaurinianae. In: Crelles Journal for pure and applied mathematics 12 (1834), pp. 263–272.
3. ↑ L. Tits: Sur la sommation des puissances numériques. In: Mathesis 37 (1923), pp. 353-355.
4. ^ Anthony William Fairbank Edwards: A quick route to sums of powers. In: American Mathematical Monthly 93 (1986), pp. 451-455. JSTOR 2323466