Let k be a positive integer. Show that 1^k + 2^k + 3^k + ... + n^k is

O(n^k+1).

Printable View

- Oct 9th 2008, 06:37 PMaaronrjBig O Proof
Let k be a positive integer. Show that 1^k + 2^k + 3^k + ... + n^k is

O(n^k+1). - Oct 9th 2008, 07:50 PMTwistedOne151
Consider the integral $\displaystyle \int_0^{n}x^k\,dx$. Suppose we consider a Riemann sum with the interval divided into n rectangles of width 1, and with the height of the rectangles being the value of the integrand at the right side of each subdivision. Then this sum is an upper bound on the integral (as our function is increasing on our interval, because k>0), and is equal to $\displaystyle 1^k+2^k+\ldots+n^k$, our sum. Thus $\displaystyle \int_0^{n}x^k\,dx<{1^k+2^k+\ldots+n^k}$.

Now, let us similarly do the Riemann sum with n subdivisions of width 1, but this time let the height of the rectangles be the value at the left side of each. Then we have a lower bound on our integral, and our sum is $\displaystyle 0^k+1^k+2^k+\ldots+(n-1)^k$. Thus

$\displaystyle 1^k+2^k+\ldots+(n-1)^k<\int_0^{n}x^k\,dx$

and by replacing n with n+1, we find

$\displaystyle 1^k+2^k+\ldots+n^k<\int_0^{n+1}x^k\,dx$

Thus

$\displaystyle \int_0^{n}x^k\,dx<{1^k+2^k+\ldots+n^k}<\int_0^{n+1 }x^k\,dx$

Do both of those integrals, and the resulting bounds will allow you to show that the sum is O(n^(k+1))

--Kevin C. - Oct 10th 2008, 03:35 AMLaurent