I was working on a problem which involves computation power sum (summation of $k^{th}$ power of first natural number), can someone help me how to simplify the below equation.

I can compute power sum $n^k$ efficiently.

Below is the given equation

$$f(0,n,k)=n^k$$ $$f(m,n,k)=\sum_{i=0}^n f(m-1,i,k)$$

Problem link

16686. Some Sums

  • 2
    $\begingroup$ I'm sorry I clicked the problem link. The fictional scenario in which this problem comes up is beyond ludicrous. $\endgroup$ Jun 8, 2014 at 16:16
  • $\begingroup$ What is the question? $\endgroup$
    – John M
    Jun 9, 2014 at 2:46
  • $\begingroup$ In order to solve this problem we need some precomputation and answering every query in O(k) time or O(k log k) , So I think this summation can be reduced to some simple form of n^k. $\endgroup$
    – Lakshman
    Jun 10, 2014 at 8:26


You must log in to answer this question.

Browse other questions tagged .