How to calculate $1^k+2^k+3^k+\cdots+N^k$ with given values of $N$ and $k$? [duplicate]

Here $1<N<10^9$ and $0<k<50$

So we have to calculate it in order of $O(\log N)$.

-

marked as duplicate by MJD, Amzoti, Dennis Gulko, Norbert, Davide GiraudoMar 10 '13 at 20:10

–  JavaMan Mar 10 '13 at 18:24
Also math.stackexchange.com/questions/18983/… and math.stackexchange.com/questions/65861/… and probably several others. –  MJD Mar 10 '13 at 18:56

The multiply-by-$n$ operator $xD$, is defined by $$(xD)^k f \rightarrow^{ops} \{n^k a_n\}_{n\geq 0}$$ where $f$ is a ordinary power series (ops) generating function for $\{a_n\}_0^\infty$. That means that $f = \sum_n a_n x^n$.
Begin with the fact that $$\sum_{n=0}^{N} x^n= \frac{x^{N+1} - 1}{x-1}$$
Then, apply $(xD)^k$ operator both sides of this relation and then set $x=1$, $$\sum_{n=1}^{N} n^k = (xD)^k \left\{{\frac{x^{N+1}-1}{x-1}}\right\}|_{x=1}$$ By, example, for $k=2$, then $$\sum_{n=1}^{N} n^2 = \frac{N(N+1)(2N+1)}{6}$$