Lower bound on $1^k+2^k+\dots+n^k$

I calculated the worst case scenario of a time complexity of an algorithm problem using recurrence tree. (The problem cannot be solved by master theorem.)

Now I want to find a lower bound on the expression I got. Specifically, I want to prove that

$$ 1^k + 2^k + \dots + n^k = \Omega(n^{k+1}). $$

You can estimate your sum from below by
$$
1^k + \cdots + n^k \geq \sum_{m=\lceil n/2 \rceil}^n n^k \geq \frac{n}{2} \cdot \left(\frac{n}{2}\right)^k = \Omega(n^{k+1}).
$$
It is even easier to see that $1^k + \cdots + n^k \leq n^{k+1}$, and so $1^k + \cdots + n^k = \Theta(n^{k+1})$.

You can get better bounds by approximating the sum with an integral:
$$
\frac{n^{k+1}}{k+1} = \int_0^n x^k \, dx \leq 1^k + \cdots + n^k \leq\int_1^{n+1} x^k \, dx = \frac{(n+1)^{k+1}-1}{k+1}.
$$
This shows that
$$
1^k + \cdots + n^k = \frac{n^{k+1}}{k+1} + O(n^k).
$$

There is also an exact formula, known as Faulhaber's formula.

StackExchange Computer Science Q#106904, answer score: 7