Big O Proof

**aaronrj** · October 9th 2008, 06:37 PM

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

**TwistedOne151** · October 9th 2008, 07:50 PM

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.

**Laurent** · October 10th 2008, 03:35 AM

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}$ .

Thread: Big O Proof

LinkBack

Thread Tools

Display

Big O Proof

Similar Math Help Forum Discussions

Proof theory: example of an existence proof of a proof?

Convert the following equational proof into a Hilbert Proof

[SOLVED] direct proof and proof by contradiction

Proof with algebra, and proof by induction (problems)

proof that the proof that .999_ = 1 is not a proof (version)

Search Tags