how to prove $\sum_{i=1}^n i^k =\Theta(n^{k+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\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?!  
 A: 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} .$$
A: 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}$
A: 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$.)
