Results 1 to 5 of 5

Math Help - Big O puzzler

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    9

    Big O puzzler

    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) )
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by othnin View Post
    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}.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2009
    Posts
    9
    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!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by othnin View Post
    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}.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2009
    Posts
    9
    Thanks guys. I think I can get a proof out of it now.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A new calculus puzzler for you
    Posted in the Math Puzzles Forum
    Replies: 8
    Last Post: February 2nd 2011, 02:09 AM
  2. puzzler
    Posted in the Math Challenge Problems Forum
    Replies: 1
    Last Post: December 8th 2005, 09:08 AM
  3. problem puzzler
    Posted in the Math Challenge Problems Forum
    Replies: 8
    Last Post: October 31st 2005, 11:25 AM
  4. X's and O's puzzler
    Posted in the Math Challenge Problems Forum
    Replies: 7
    Last Post: September 22nd 2005, 12:41 AM
  5. 4 4's Puzzler
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: September 8th 2005, 12:21 PM

Search Tags


/mathhelpforum @mathhelpforum