how to prove $\sum_{i=1}^n i^k =\Theta(n^{k+1})$

Question

we can say that if all $i$ s in the sum were equal to $n$ then the answer to the summation would be $n\cdot n^k$. So $n^{k+1}$ is the upper bound.so $\displaystyle\sum_{i=1}^n i^k=O(n^{k+1})$

For the lower bound : we obviously know that $\displaystyle n^k<\sum_{i=1}^n i^k$. so we can say that $\displaystyle\sum_{i=1}^n i^k=\omega(n^k)$.

Now if we could prove that cases like $\displaystyle\sum_{i=1}^n i^k=\Theta(n^k\cdot \log(n))$ is not possible (meaning the $\displaystyle\sum_{i=1}^n i^k$ has a polynomial growth) the problem would be solved right?!

Answer 1

we can say that if all i s in the sum were equal to n then the answer to the summation would be n⋅nk. So nk+1 is the upper bound.so $\displaystyle\sum_{i=1}^n i^k=O(n^{k+1})$

For the lower bound : we know that $\displaystyle n^k<\sum_{i=1}^n i^k$ . so we can say that $\displaystyle\sum_{i=1}^n i^k=\Omega(n^k)$.

now if we write $1^k$ as $(n-n+1)^k$ and so on we can conclude that $\displaystyle\sum_{i=1}^n i^k$ is a polynomial thus it has a polynomial growth.

so its growth must be same as $n^{k+1}$

Answer 2

You can get the upper bound by $$1^p + 2^p + ... + n^p \le n^p + n^p + ... + n^p = n \ n^p = n^{p+1}$$

and you can get the lower bound by doing a similar thing after throwing away the first half of the sum

$$1^p + ... + (\frac n 2)^p + ... + n^p \ge (\frac n 2)^p + ... + n^p \ge (\frac n 2)^p + ... + (\frac n 2)^p = \frac n 2 \ (\frac n 2)^p = {(\frac n 2)}^{p+1} .$$

Answer 3

To prove $$\sum_{i=1}^n i^k =\Theta(n^{k+1})\tag1$$ you need to show that the following inequality is valid for all $n$ sufficiently large: $$a\le \frac{\sum_{i=1}^n i^k}{n^{k+1}}\le A,\tag2$$ where $a$ and $A$ are positive constants. This follows from the fact that the expression at the center of (2) can be written as a Riemann sum: $$\frac{\sum_{i=1}^n i^k}{n^{k+1}}=\frac1n\sum_{i=1}^n \left({\frac in}\right)^k\tag3$$ which converges as $n\to\infty$ to the integral $\int_0^1 x^k\,dx=\frac1{k+1}$.

(To finish off, use the result: If $(x_n)$ is a sequence such that $x_n\to c$ with $c$ positive, then $x_n\le 2c$ for all sufficiently large $n$. Apply the result again to the sequence $(\frac 1{x_n})$ to conclude $x_n \ge \frac c2$ for all large $n$.)