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

Question

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

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

Answer 1

Very interesting question, using generating functions

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} $$