Show that $1^k + 2^k + ... + n^k$ is $\cal O(n^{k+1})$ , using an integral.

Asked Sep 20 '17 at 16:51

Active Sep 20 '17 at 16:59

Viewed 428 times

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

Hi, I know that $f(i) ≤ \int\limits_{1}^{n+1}x^{k}dx$

When I integrate f(i) using this rule, I get $\frac{((n+1)^{k+1}-1)}{(k+1)}$

How do I use this information to prove that $f(i)$ is $O(n^{k+1})$?

(the use of the integral is required for this problem by my teacher)

edited Sep 20 '17 at 16:59

asked Sep 20 '17 at 16:51

big papi

1

https://math.stackexchange.com/questions/1248679/show-that-1k2k-nk-is-o-nk1?noredirect=1&lq=1, https://math.stackexchange.com/questions/1645160/show-that-1k2k-cdotsnk-is-omega-nk1?rq=1 ask the same question. – StubbornAtom Sep 20 '17 at 16:54
Possible duplicate of Show that $1^k+2^k+\cdots+n^k$ is $\Omega (n^{k+1})$. – Dietrich Burde Sep 20 '17 at 16:57

0 Answers0