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

<p>Define $S_k$ by</p>

<p>$$S_k = {1 \choose k} + {2 \choose k} + \dots + {n \choose k} = {n+1 \choose k+1}.$$</p>

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

<p>Similarly,</p>

<p>$$S_{k-1} = {1 \choose k-1} + {2 \choose k-1} + \dots + {n \choose k-1} = {n+1 \choose k},$$</p>

<p>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}$).</p>

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

<p>Furthermore, we can find constants $c_0,\dots,c_k$ such that</p>

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

<p>holds for all $x$.  It follows that</p>

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

<p>which can be computed in $O(k)$ time.</p>

CC BY-SA 3.0
2012-11-21T08:42:35.927Z
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...)
user197284
CC BY-SA 3.0
2012-11-20T23:12:09.247Z
2012-11-20T23:12:09.247Z
D.W.
<p>I know some schemes to compute <a href="http://en.wikipedia.org/wiki/Power_sum_symmetric_polynomial" rel="nofollow">power sums</a> (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 <a href="http://en.wikipedia.org/wiki/Bernoulli_number" rel="nofollow">Bernoulli numbers</a>, 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)</p>

<p>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.</p>

<p><em>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)</em></p>

<p>Thank you very much!</p>

<ds.algorithms><co.combinatorics><universal-computation>
Computing power sums
user197284
# Computing power sums

(Asked by: username_0 on 2012-11-14)

I know some schemes to compute [power sums](http://en.wikipedia.org/wiki/Power_sum_symmetric_polynomial) (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](http://en.wikipedia.org/wiki/Bernoulli_number), 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!

**Tags:** ds.algorithms, co.combinatorics, universal-computation

---

## 1 answers

### Answer by username_1 on 2012-11-20. Score: 2

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.

> **Comments:**
> **username_0**: 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...)  

---

