# Show that $1^k+2^k+...+n^k$ is $O (n^{k+1})$.

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?

• That's a fine answer. Apr 23, 2015 at 17:47
• 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). Apr 23, 2015 at 17:51
• I suppose it is big-$O$. Apr 23, 2015 at 17:54
• You know this thing is $\sim \frac{n^{k+1}}{k+1}$? Apr 23, 2015 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. Oct 24 at 21:58