Big O puzzler

**othnin** · March 19th 2009, 10:08 AM

I have the following problem and I am stuck on it. Any ideas on how to work it?

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

**Opalg** · March 20th 2009, 06:36 AM

Originally Posted by othnin

I have the following problem and I am stuck on it. Any ideas on how to work it?

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

You want to show that $\frac{\sum_{r=1}^nr^k}{n^{k+1}}$ is bounded as $n\to\infty$ . One way is to write that expression as $\frac1n\sum_{r=1}^n\Bigl(\frac rn\Bigr)^k$ and think of it as a Riemann sum approximating $\int_0^1\!\!x^k = \frac1{k+1}$ .

**othnin** · March 20th 2009, 12:33 PM

Interesting,

I was trying to do a proof by Induction. Do you know if it's possible to it that way?
Thanks for heads up!

**Laurent** · March 21st 2009, 03:52 AM

Originally Posted by othnin

I have the following problem and I am stuck on it. Any ideas on how to work it?

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

Another way is the following easy one: since $i^k\leq n^k$ for $i=1,\ldots,n$ , we have

$1^k+2^k+\cdots+n^k\leq n^k+n^k+\cdots+n^k= n\cdot n^k = n^{k+1}$ .

**othnin** · March 21st 2009, 02:22 PM

Thanks guys. I think I can get a proof out of it now.

Thread: Big O puzzler

LinkBack

Thread Tools

Display

Big O puzzler

Similar Math Help Forum Discussions

A new calculus puzzler for you

puzzler

problem puzzler

X's and O's puzzler

4 4's Puzzler

Search Tags