# Growth rate of integer power sum

1. Jan 29, 2010

### Thomas_

I need to show that

$$\sum_{i=0}^n i^k=\Theta(n^{k+1})$$

Or equivalently

$$\lim_{n\to\infty}\frac{\sum_{i=0}^n i^k}{n^{k+1}}=C$$

I simply don't know what to do with the sum here. I know that I can rewrite or expand it, but that doesn't seem to help me. Any suggestions?

Thank you!

2. Jan 29, 2010

### Dick

You could think of the integer sum as a lower sum for an integral of f(x)=x^k.