General formula for natural power summation

Question

Where can I find the formula for $$\sum n^k$$ and subsequently the formula for $$\sum (a+(n-1)d)^k$$

for $k \in N$ along with corresponding proofs.

Answer 1

According to your Wikipedia article in the comments,

A rigorous proof of these formulas and his assertion that such formulas would exist for all odd powers took until Carl Jacobi (1834).

So we only have a guaranteed formula for odd powers. But, if you wanted to know, Mathworld also has a not-so-concise form that holds for all odd powers:

\begin{align} 1^{p} + 2^{p} &+ 3^{p} + \cdots + n^{p}\\ &= \frac{1}{p+1} \sum_{i=1}^{p+1} (-1)^{\delta_{i\space p}} \binom{p+1}{i} B_{p+1-i}n^i. \end{align}

where $B_i$ is the $i$th Bernoulli number.

The reason there is no concise formula is because if you notice the coefficients for most of the formulas are very different, so the general formula must contain some way to generate these coefficients.

Answer 2

there are many, I'll post some

[1-Using derivatives]

$$s(n) = \sum^{n}_{k=0} k^p =\sum^{p+1}_{k=1}a_k n^k $$

where $$ a_{t+1} =\frac{1}{t+1}\sum^{p+1}_{k=t+2}a_k{ k \choose t} (-1)^{k-t}\;\; ,\;\; a_{p+1}=\frac{1}{p+1}. $$

Proof:

From $s(n) = \sum\limits^{n}_{k=0} k^p $, then $s(n) -s(n-1)=n^p $. Let's suppose $s(n)= \sum\limits^{p+1}_{k=1}a_k n^k $ which has the independent term $a_0=0$ because $s(0) =0$. We apply the $p$-th derivative in $s(n) -s(n-1)=n^p $ which results in $$s^{(p)}(n) -s^{(p)}(n-1) =p! $$ we have $s^{(p)}(n) = a_p.p! + a_{p+1}(p+1)!n$ so $s^{(p)}(n) -s^{(p)}(n-1) (n)=a_{p+1}(p+1)!=p! $ which implies $a_{p+1}=\frac{1}{(p+1)} .$

We will find the other coefficients. We take the $t$-th derivative in $s(n) -s(n-1)=n^p$, with $0 \leq t<p$, so $$s^{(t)}(n) -s^{(t)}(n-1) =t!{p \choose t} n^{p-t} $$, taking $n=0$ we have $$s^{(t)}(0) =s^{t}(-1) $$

Using $s(n)= \sum\limits^{p+1}_{k=1}a_k x^k $ and applying again the $t$-th derivative $$ s^{(t)} (n)= \sum^{p+1}_{k=t}a_k(t!){ k \choose t} n^{k-t}$$ de $s^{(t)}(0) =s^{t}(-1) $ follow $$ \sum^{p+1}_{k=t}a_k(t!){ k \choose t} 0^{k-t} = \sum^{p+1}_{k=t}a_k(t!){ k \choose t} (-1)^{k-t} \Rightarrow $$ $$ a_t.t! = t!\sum^{p+1}_{k=t+2}a_k{ k \choose t} (-1)^{k-t} + a_t(t!)-a_{t+1}(t+1)! \Rightarrow$$ $$ a_{t+1} =\frac{1}{t+1}\sum^{p+1}_{k=t+2}a_k{ k \choose t} (-1)^{k-t} $$ as we wanted to show.

[2-Using Bernoulli numbers]

$$ \sum^{n-1}_{k=0}k^p=\frac{1}{(p+1)}\sum^{p}_{k=0}{p+1 \choose k}B_k .n^{p-k+1}.$$

[ Bernoulli Numbers]

The Bernoulli numbers are defined by the generating function

$$\frac{x}{e^{x}-1} =\sum^{\infty}_{n=0}B_{n}\frac{x^{n}}{n!}$$ (we will you use that definition)

Proof:

We define the function $$f_n(x)=\frac{x(e^{nx}-1)}{e^x -1}. $$ We have $\sum\limits^{n-1}_{k=0}x^k=\frac{x^{n}-1}{x-1}$, so take $x=e^x$ it follows $\sum\limits^{n-1}_{k=0}e^{xk}=\frac{e^{x.n}-1}{e^x-1}$ , then $$f_n(x)=x\sum\limits^{n-1}_{k=0}e^{xk} $$ using the series $e^z=\sum\limits^{\infty}_{t=0}\frac{z^t}{t!} $ taking $z=xk$ follows $$e^{x.k}=\sum^{\infty}_{t=0}\frac{x^t.k^t}{t!} $$ replacing in $f_n(x)$ we have $$f_n(x)=x \sum^{n-1}_{k=0}\sum^{\infty}_{t=0}\frac{x^t.k^t}{t!}= \sum^{\infty}_{t=0}(\sum^{n-1}_{k=0}\frac{k^t}{t!})x^{t+1}$$ then the coefficient of $x^{p+1}$ is $\sum\limits^{n-1}_{k=0}\frac{k^p}{p!}.$

We have $$f_n(x)=\frac{x(e^{nx}-1)}{e^x -1}=(\sum^{\infty}_{k=0}\frac{B_kx^k}{k!} ) (\sum^{\infty}_{k=1}\frac{x^k n^k}{k!} )=x(\sum^{\infty}_{k=0}\frac{B_kx^k}{k!} ) (\sum^{\infty}_{k=0}\frac{x^k n^{k+1}}{(k+1)!} )$$

The product of the last two series is $\sum\limits^{\infty}_{k=0}c_k x^k $, where $$c_p=\sum^{p}_{k=0}\frac{B_k .n^{p-k+1}}{k! (p-k+1)!} $$

is the coefficient of $x^{p+1}$. Comparing with the coefficient of the other series $$\sum^{n-1}_{k=0}\frac{k^p}{p!}=\sum^{p}_{k=0}\frac{B_k .n^{p-k+1}}{k! (p-k+1)!} $$ follows $$\sum^{n-1}_{k=0}k^p=\frac{1}{(p+1)}\sum^{p}_{k=0}\frac{B_k .n^{p-k+1}p!(p+1)}{k! (p-k+1)!}=\frac{1}{(p+1)}\sum^{p}_{k=0}{p+1 \choose k}B_k .n^{p-k+1}. $$

Then we have the result $$ \sum^{n-1}_{k=0}k^p=\frac{1}{(p+1)}\sum^{p}_{k=0}{p+1 \choose k}B_k .n^{p-k+1}.$$

Extra:\Edited:

There are other ways to find. 3-Using the euler maclaurin summation $$\sum f(x)=B_{0}\int f(x) +\sum^{\infty}_{k=0}B_{k+1}.\frac{D^{k}}{(k+1)!}f(x) +c$$ $B_{k}$ here is also a bernoulli number.

4- Using the Worpitzky identity $$x^{n}=\sum^{n}_{k=0}\bigg<^{n}_{k} \bigg> {x+k\choose n} .$$ And the summation of binomials (it's easy to sum binomial) here $\bigg<^{n}_{k} \bigg>$ are eulerian numbers

5-Using Newton interpolation formula

$$f(x+n)=\sum^{n}_{k=0}{n \choose k}\Delta^k f(x) $$ we can apply that to the sum direclty or in any term $x^k$ to write it as the sum of binomial coefficients. (in that way the stirling numbers of second kind appear)

Answer 3

Too long for a comment.

Concerning $$S_k=\sum _{i=1}^n (a+ (i-1)d)^k$$ the problem is still worse but, for given $k$, you can "easily" derive nice formulae $$S_1= \left(a-\frac{d}{2}\right)n+\frac{d }{2}n^2$$ $$S_2= \left(a^2-a d+\frac{d^2}{6}\right)n+ \left(a d-\frac{d^2}{2}\right)n ^2+\frac{d^2 }{3}n^3$$ $$S_3= \left(a^3-\frac{3 a^2 d}{2}+\frac{a d^2}{2}\right)n+\frac{1}{4} \left(6 a^2 d-6 a d^2+d^3\right)n^2+ \left(a d^2-\frac{d^3}{2}\right)n^3+\frac{d^3 }{4}n^4$$ and so on.

For sure, if $a=0$, these reduce to Faulhaber's formulae (multiplied by $d^k$)