# Computing power sums

I know some schemes to compute power sums (I mean $1^k + 2^k + ... + n^k$) (here I assume that every integer multiplication can be done in $O(1)$ time for simplicity): one using just fast algorithm for computing $n^k$ in $O(\lg k)$ and it's overall time is $O(n \lg k)$, the other, using Bernoulli numbers, can be implemented in $O(k^2)$. And the most complicated works in $O(n \lg \lg n + n \lg k / \lg n)$ - it uses somewhat like sieve of Eratosthenes. (Don't know if it's well-known, I came up with this by myself, so if it not well-known, I can explain how to do it)

Every of this 3 algorithms, but the first, has it's own pros and cons, for example for every $k = n^{O(1)}$ the last algorithm works in $O(n \lg \lg n)$ time, while first in runs $O(n \lg n)$ and second is even worse. When $k = o(\sqrt{n \lg \lg n})$ second algorithm performs better than others.

So my question is: if there exists some more efficient algorithms? (Like in previous problems, I am not merely interested in asymptotics in $n$, but in $k$ too)

Thank you very much!

-

Here's another approach, which I think runs in $O(k)$ time.

Define $S_k$ by

$$S_k = {1 \choose k} + {2 \choose k} + \dots + {n \choose k} = {n+1 \choose k+1}.$$

The right-hand-side can be computed in $O(k)$ time.

Similarly,

$$S_{k-1} = {1 \choose k-1} + {2 \choose k-1} + \dots + {n \choose k-1} = {n+1 \choose k},$$

and given the value of the previous sum $S_k$, we can compute this sum $S_{k-1}$ in $O(1)$ time (using the fact that ${n+1 \choose k} = {n+1 \choose k+1} \times {k+1 \over n-k+1}$).

In this way, we can compute all of the sums $S_k,\dots,S_2,S_1,S_0$ in $O(k)$ time.

Furthermore, we can find constants $c_0,\dots,c_k$ such that

$$x^k = c_k {x \choose k} + \dots + c_1 {x \choose 1} + c_0 {x \choose 0}$$

holds for all $x$. It follows that

$$S = 1^k + 2^k + \dots + n^k = c_k S_k + \dots + c_1 S_1 + c_0 S_0,$$

which can be computed in $O(k)$ time.

-
Wow! But how can you compute $c_k$ in $O(k)$ time? I know how to do it in $O(k^2)$ (2 algorithms), the first is to exploit solving triangular system (just plug in the equation $0$, $1$, ..., $k$, this system is triangular). And the second is that coefficients of this representation are Stirling numbers of second kind, and there is a recurrence for them similar to the recurrence of binomial coefficients, which help them to be computed in $O(k^2)$. (Sure there is scheme, described by you, which can compute binomial coeff. in $O(k)$, but I wonder if there exists similar to Stirling numbers...) –  Sergey Finsky Nov 21 '12 at 8:42