General form for sum of powers

Question

Given integers $h$ and $p$, is there a general way to write $f(h,p)$ such that:$$f(h,p)=\sum_{n=1}^h{n^p}$$

I know the equations for $p\leq5$:

$$f(h,1)=\sum_{n=1}^hn={h(h+1)\over2}\\f(h,2)=\sum_{n=1}^hn^2={f(h,1)(2h+1)\over3}\\f(h,3)=\sum^h_{n=1}n^3=f(h,1)^2\\f(h,4)=\sum^h_{n=1}n^4={f(h,2)(3h^2+3h-1)\over5}\\f(h,5)=\sum^h_{n=1}n^5=2f(h,2)f(h,3)$$

I cannot spot any sort of pattern.

Answer 1

Yes. It's called Faulhaber's formula.

Essentially,

$$f(h,p)=\frac{h^{p+1}}{p+1}+\tfrac12h^p+\sum_{k=2}^p\frac{B_k}{k!}h^{p-k+1}\prod_{i=0}^{k-2}(p-i)$$

Where $B_k$ are the Bernoulli numbers. It looks complicated, but it essentially writes $f$ as a polynomial in $h$.

Answer 2

The generalization is called Faulhaber's formula and can be derived one from the previous by a nice telescopic trick.

For example for $\sum k^2$ note that

$$(k+1)^3-k^3=3k^2+3k+1 \implies n^3-1=3\sum_{k=1}^{n} k^2+3 \sum_{k=1}^{n} k +n $$

from which $\sum_{k=1}^{n} k^2$ can be derived.

The latter argument prove that $\sum_{k=1}^{n} k^m$ is expressed by a polynomial of degree $m+1$.

Answer 3

This sum can be expressed as Faulhaber's formula : $$f(h,p)=\sum_{n=1}^h{n^p}=\frac1{p+1}\sum_{j=0}^p\binom{p+1}j B_j\, h^{p+1-j},$$ where $B_j$ is the $j$-th Bernoulli number, with the convention that $B_1=\frac12$, not $-\frac12$.

The generating series for the Bernoulli numbers is the expansion of $$\frac x{\mathrm e^x-1}=\sum_{j=0}^\infty B_j\frac{x^j}{j!}.$$

Answer 4

I agree with the previous answers. However, an elementary direct derivation is possible that avoids bernoulli numbers and calculus and relies on mathematical induction. The following assertion is known to be true:

Given any positive integer k, there exist rational numbers $c_0, c_1, \cdots, c_k$ such that $\forall n\in\mathbb{Z^+}, \sum_{i=0}^n i^k = c_0n^{k+1} + c_1n^k + \cdots + c_kn^1.$
Given a specific value of $k$, you only need to use mathematical induction to derive $c_0, c_1, \cdots, c_k.$

As an example, I will derive $c_0, c_1, c_2, c_3$ for $k=3.$ It is clear that for any coefficients $c_0, \cdots, c_3,$ the formula will be true for n=0. Therefore, it is sufficient to derive coefficients so that if the formula is true for n=N, then the formula must also be true for n=N+1.

By the inductive assumption, $\sum_{i=0}^{N+1} i^3 = c_0N^4 + c_1N^3 + c_2N^2 + c_3N + (N+1)^3.$
$c_0, \cdots, c_3$ must be derived so that the above expression is equal to
$c_0(N+1)^4 + c_1(N+1)^3 + c_2(N+1)^2 + c_3(N+1).$

Grouping expressions by powers of N:
$c_0N^4 = c_0N^4$
$N^3(c_1 + 1) = N^3(4c_0 + c_1)$
$N^2(c_2 + 3) = N^2(6c_0 + 3c_1 + c_2)$
$N^1(c_3 + 3) = N^1(4c_0 + 3c_1 + 2c_2 + c_3)$
$N^0(1) = N^0 (c_0 + c_1 + c_2 + c_3)$

This simplifies to the following 4 linear equations in 4 unknowns:
$1 = 4c_0$
$3 = 6c_0 + 3c_1$
$3 = 4c_0 + 3c_1 + 2c_2$
$1 = 1c_0 + 1c_1 + 1c_2 + 1c_3$

The above pattern (where both the right hand side coefficients and the left hand side coefficients come directly from pascal's triangle) will prevail for any positive integer k. Further, for any positive integer k, the resulting (k+1) linear equations in (k+1) unknowns will permit a direct iterative solution. For example, in this case

$c_0 = 1/4,$ so $c_1 = 1/2$, so $c_2 = 1/4,$ so $c_3 = 0.$

A non-calculus-algebra-only derivation of Bernoulli numbers occurs by noticing that if you make the change of variable: $c_0 = \frac{1}{k+1}a_0, \;c_1 = a_1,\;$ and $\;c_i = \frac{k!}{(i-1)!(k+1-i)!}a_i\;\;$ [for $i>1$]:

Then you will end up with the same equations regardless of the value of k. This leads to a "universal" set of coefficients that can be applied to any value of k. Apparently, this was discovered by Bernoulli in the 1700's, when calculus was just developing.