Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I read here that in the tenth property:

http://www.cs.auckland.ac.nz/~jmor159/PLDS210/latex/complexity.pdf

The sum of the first $nr^{th}$ powers grows as the $(r+1)^{th}$ power

This is not very intuitive to me, why is that?

Since the base is changing (not the exponent) in the summatory I can't solve it with a geometric series

share|improve this question
    
It is a good exercise to prove that $p(r)=\sum_{i=1}^{n}k^r$ is a polynomial with leading term of $$\frac{n^{r+1}}{r+1}$$ –  Pedro Tamaroff Aug 10 '12 at 18:39

3 Answers 3

up vote 2 down vote accepted

For intuition, think about converting your sum to an integral. $\sum_{i=0}^n i^r \approx \int_0^n i^r di=\frac 1{r+1}n^{r+1}$

If you try it for small values, for $r=0$ you get the sum of $n \ 1$'s, which is $n$ (growing like $r+1=1$). For $r=1$ you get the triangular numbers $\frac {n(n+1)}2$, (growing like $r+1=2$).

share|improve this answer

$\sum_{k=1}^{n}k^r \ge \int_{k=0}^{n}k^rdr = \frac{n^{r+1}}{r+1}$ (to see why this first inequality holds, note that $\int_{k=i}^{i+1}k^rdr \le \int_{k=i}^{i+1}({i+1})^rdr = (i+1)^r$

On the other hand, $\sum_{k=1}^{n}k^r \le \sum_{k=1}^{n}n^r = n^{r+1}$

So as you can see, the sum is bounded both below and above by some constant multiple of $n^{r+1}$.

share|improve this answer

If you don't want to bring out the big guns and would be happy with a big-O estimate when $r\ge 0$, you could simply argue that $$ 1^r+2^r +\cdots +n^r\le \underbrace{n^r+n^r+\cdots+n^r}_n = n\cdot n^r=n^{r+1} $$ so by definition $\sum_{k=1}^n k^r = O(n^{r+1}).$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.