Let $k$ be a positive integer. Show that $1^k+2^k+...+n^k$ is $O (n^{k+1})$.

So according to the definition of big-$O$ notation we have:

$$1^k+2^k...+n^k ≤ n(n^k) = n^{k+1}$$

whenever $n>1$

Is this a satisfied answer? can someone help?

  • 10
    $\begingroup$ That's a fine answer. $\endgroup$ Commented Apr 23, 2015 at 17:47
  • 1
    $\begingroup$ If you just want big-O, then your answer is fine. If you want big-Theta (i.e. the sum is also lower bounded by $cn^{k+1}$ for some constant $c > 0$, that is a harder problem. Sometimes even professors confuse big-O and big-Theta, so make sure that all you have to do is big-O (upper bound). $\endgroup$ Commented Apr 23, 2015 at 17:51
  • $\begingroup$ I suppose it is big-$O$. $\endgroup$ Commented Apr 23, 2015 at 17:54
  • $\begingroup$ You know this thing is $\sim \frac{n^{k+1}}{k+1}$? $\endgroup$ Commented Apr 23, 2015 at 18:17
  • $\begingroup$ I have this exact same question, but don't understand this (def not saying it's wrong - only it's too concise for novice and I don't get it). How does this prove it? Explaining it like I'm 5yrs old would be welcomed. $\endgroup$
    – Mote Zart
    Commented Oct 24, 2023 at 21:58


You must log in to answer this question.

Browse other questions tagged .