9

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?

Alim Teacher
  • 1,261
  • 10
    That's a fine answer. – Antonio Vargas Apr 23 '15 at 17:47
  • 1
    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). – user2566092 Apr 23 '15 at 17:51
  • I suppose it is big-$O$. – Alim Teacher Apr 23 '15 at 17:54
  • You know this thing is $\sim \frac{n^{k+1}}{k+1}$? – ncmathsadist Apr 23 '15 at 18:17
  • 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. – Mote Zart Oct 24 '23 at 21:58

0 Answers0