# Big Omega Notation Proof

Can someone show me how to start this off? I need to prove it, but I'm not sure how I would prove Big Omega.

Prove that $f(n)=\sum_{i=1}^ni^k\in\Omega(n^{k+1})$.

Thank you for the help!

-

## migrated from mathoverflow.netOct 20 '13 at 0:44

This question came from our site for professional mathematicians.

Note that $$\displaystyle\sum_{i = 0}^n i^k \geq \displaystyle\sum_{i = n/2}^n i^k \geq \displaystyle\sum_{i = n/2}^n \left(\frac{n}{2}\right)^k = \left(\frac{n}{2}\right)^{k+1}$$
I'll let you work out how to use that to get $\Omega(n^{k+1})$. (Remember that $k$ is a constant.)
You can adjust the lower bound on the second and third sums to make the end result on the right exactly $\left(\frac{n}{2}\right)^{k+1}$; as posted it might be a slight bit off (though it doesn't affect the end result). –  Dennis Meng Oct 20 '13 at 1:05