Show that $1^k+2^k+\cdots+n^k$ is $\Omega (n^{k+1})$

Question

...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})$?

Answer 1

$\frac{n^{k+1}}{k+1}=\int\limits_{0}^nx^kdx\leq1^k+2^k+\dots +n^k\leq \int\limits_{1}^{n+1}x^{k}dx=\frac{(n+1)^{k+1}-1}{k+1}$.

It is clear all monic polynomials of degree $k+1$ are asymptotically equivalent, so the result follows.

Answer 2

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.