Results 1 to 11 of 11

Math Help - Big theta proof

  1. #1
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    Question Big theta proof

    Hi,

    I need some help with this big theta proof:

    Show that f(n) = summation (from h=1 to n) of h3/2h is big theta(1).

    What I got so far:

    omega(g(1)) <= f(n) <= O(g(1))
    c1g(1) <= f(n) <= c2g(1)

    For f(n) <= O(1)
    f(n) = summation (from h=1 to n) of h3/2h <= 1c2
    f(n) = 1/2 + 8/4 + ... + n3/2n <= c2
    1/2 <= c2 and 8/4 <= c2 ... and n3/2n <= c2

    Since n3/2n is the biggest term in the summation, then showing n3/2n <= c2 is enough to show that f(n) <= O(1).
    And here is where I get stuck, I'm not sure what to do next...
    Last edited by Sneaky; January 20th 2013 at 04:52 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    539
    Thanks
    218

    Re: Big theta proof

    Your assertion that {h^3\over 2^h} is increasing is unfortunately false. In fact the given sequence is decreasing for h > 5 -- examine the function f(x)={x^3\over 2^x}.

    Entirely new direction: does \sum^\infty_{h=1}{h^3\over 2^h} converge? If so, does this mean your partial sums are \Theta(1)?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    Re: Big theta proof

    Oh ok, I see that when h > 5, it decreases. It then converges at 0 when h -> infinity.

    But how can I evaluate the limit of the summation at h = infinity?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    539
    Thanks
    218

    Re: Big theta proof

    Let S(n)=\sum^n_{h=1}{{h^3\over 2^h}. Then to say the series converges is to say the limit as n approaches infinity of S(n) is some finite value s -- you don't need to know specifically the value of s. So there is an N such that for {n\geq N}, s-1<S(n)<s+1. So c_1=s-1 and c_2=s+1 satisfy the requirement of \Theta. Remember \Theta requires the inequality only for all n\geq N; i.e. only for "large" values of n.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    Re: Big theta proof

    But for this, don't you need to show that limit is a finite number? How can this be done?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    539
    Thanks
    218

    Re: Big theta proof

    When we say a series converges, we mean \lim_{n\rightarrow \infty}S(n)=s, s a (finite) real number. Remember the ratio test for convergence: \lim_{h\rightarrow\infty}{(h+1)^3/2^{h+1}\over h^3/2^h}=1/2<1, so the series converges.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    Re: Big theta proof

    nevermind, I get the question now. thanks
    Last edited by Sneaky; January 21st 2013 at 05:55 PM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    Re: Big theta proof

    shouldn't it be s-1 <= s(n) <= s+1 instead of s-1 < s(n) < s+1 ?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    539
    Thanks
    218

    Re: Big theta proof

    Yes and no; see the attachment:

    Big theta proof-mhflimitexplanation.png
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    Re: Big theta proof

    I don't under stand the last two sentences.

    If s(n) (- (s-1, s+1), how is it that s(n) (- [s-1, s+1] ?

    Doesn't normal parenthesis like '(' and ')' mean, up to but not including?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    539
    Thanks
    218

    Re: Big theta proof

    Surely you know 3<4 implies 3\leq4. More generally, (0,4)\subset[0,4]; i.e. if 0<x<4 then 0\leq x\leq4.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: April 29th 2010, 09:24 AM
  2. Replies: 2
    Last Post: March 29th 2010, 06:38 AM
  3. Replies: 3
    Last Post: February 6th 2009, 03:19 PM
  4. Replies: 1
    Last Post: January 23rd 2009, 09:53 AM
  5. Solve sin4(theta) = cos2(theta)
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: December 8th 2008, 10:23 AM

Search Tags


/mathhelpforum @mathhelpforum