Show that $1^k+2^k+\cdots+n^k$ is $\Omega (n^{k+1})$ ...where k is a positive integer. The Big Oh case is not so hard. But how do I show that $1^k+2^k+\cdots+n^k$ is  $\Omega (n^{k+1})$?

Suppose $n$ is even. Bound each term of the "upper half" from below by $(n/2)^{k}$. You have $n/2$ such terms. For a lower bound of $(n/2)(n/2)^{k}= n^{k+1}/2^{k+1}$. 
The general case can be handled in the same way.
