Results 1 to 3 of 3

Math Help - Big O Proof

  1. #1
    Junior Member
    Joined
    Oct 2008
    From
    Dallas, TX
    Posts
    71

    Big O Proof

    Let k be a positive integer. Show that 1^k + 2^k + 3^k + ... + n^k is
    O(n^k+1).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Dec 2007
    From
    Anchorage, AK
    Posts
    276
    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.
    Last edited by TwistedOne151; October 9th 2008 at 08:54 PM. Reason: LaTeX error
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

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

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: October 19th 2010, 11:50 AM
  2. Replies: 0
    Last Post: June 29th 2010, 09:48 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 11:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 05:07 PM

Search Tags


/mathhelpforum @mathhelpforum