Search code examples
mathbig-oinequality

Proof big omega of 1^k+2^k+..+n^k

Question:

1^k + 2^k + ... + n^k is big omega of n^(k+1)
1^k + 2^k + ... + n^k => cn^(k+1)

Hi, I need some help to figure out how I can prove this. I am trying to avoid induction and proving it as simple as possible.

Solution

  • Use integrals. Your sum is larger than the

    integral of x^k from 0 to n

    and smaller than the

    integral of x^k from 1 to n+1.

    Thus you even get a Theta class. And c=1/(k+1).