O-notation property - sum of the first n powers growth

Question

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

Answer 1

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$).

Answer 2

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

Answer 3

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