# Big O Proof

• October 9th 2008, 06:37 PM
aaronrj
Big O Proof
Let k be a positive integer. Show that 1^k + 2^k + 3^k + ... + n^k is
O(n^k+1).
• October 9th 2008, 07:50 PM
TwistedOne151
Consider the integral $\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 $1^k+2^k+\ldots+n^k$, our sum. Thus $\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 $0^k+1^k+2^k+\ldots+(n-1)^k$. Thus
$1^k+2^k+\ldots+(n-1)^k<\int_0^{n}x^k\,dx$
and by replacing n with n+1, we find
$1^k+2^k+\ldots+n^k<\int_0^{n+1}x^k\,dx$
Thus
$\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.
• October 10th 2008, 03:35 AM
Laurent
Quote:

Originally Posted by aaronrj
Let k be a positive integer. Show that 1^k + 2^k + 3^k + ... + n^k is
O(n^k+1).

Or you can write $1^k+2^k+\cdots+n^k\leq n^k+n^k+\cdots+n^k=n\times n^k=n^{k+1}$.