# Compute growth of function [closed]

Suppose that $p>0$ and $n>0$ is a natural number. How do I prove that

$$\sum_{k=1}^n k^p = 1^p + 2^p + \dots +n^p \sim \frac{1}{p+1}n^{p+1}=\Theta(n^{p+1})$$

for $n \rightarrow \infty$?

• This seems to be a question about pure mathematics with no computational content, so I'm voting to close as off-topic. – David Richerby Dec 27 '17 at 18:30

You can show this by estimating the sum using an integral: on the one hand, $$\sum_{k=1}^n k^p = \int_1^{n+1} \lfloor x \rfloor^p \, dx \leq \int_1^{n+1} x^p \, dx = \left. \frac{x^{p+1}}{p+1} \right|_1^{n+1} = \\\frac{(n+1)^{p+1}-1}{p+1} = \frac{n^{p+1}}{p+1} + O(n^p).$$ On the other hand, $$\sum_{k=1}^n k^p = \int_0^n \lceil x \rceil^p \, dx \geq \int_0^n x^p \, dx = \left. \frac{x^{p+1}}{p+1} \right|_0^n = \frac{n^{p+1}}{p+1}.$$ You can also calculate the sum explicitly, using Faulhaber's formula.
$$\sum_{k=1}^{n}k^p<\sum_{k=1}^{n}\color{red}n^p=n\times n^p=n^{p+1}$$
• However, this misses the constant in front of $n^{p+1}$. – Yuval Filmus Dec 30 '17 at 10:12