Page 1 of 2 12 LastLast
Results 1 to 15 of 16

Math Help - Proof that a sum is bounded by given functions?

  1. #1
    Newbie
    Joined
    Jun 2013
    From
    montreal
    Posts
    10

    Proof that a sum is bounded by given functions?

    Hey there!

    I'm really stuck on a question and i can't figure out how I should solve it.
    I have a sum given by

     H_N = \sum_{i=1}^N\frac{1}{i}

    Given the special case where

     N = 2^{m+1}

    I have to prove that H_N is logarithmically bounded by

     1+\frac{\lg{N}}{2} \leq H_{N} \leq 1+\lg{N}

    And here's a *HINT* : Look at the terms

    \frac{1}{2^m+1}+...+\frac{1}{2^{m+1}}

    in H_N

    Well, I really don't get it...if someone could help me I would greatly appreciate!
    ps. I'm glad I found thoses forums, I'll certainly become an active member, being a studient in computer sciences :P.

    THANKS!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,501
    Thanks
    765

    Re: Proof that a sum is bounded by given functions?

    Prove the required claim by induction on m. This requires bounding \sum_{i=2^m+1}^{2^{m+1}}1/i from below and from above, as per the hint.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2013
    From
    montreal
    Posts
    10

    Re: Proof that a sum is bounded by given functions?

    Thank you for your reply!

    I kinda guessed it was by induction but didn't think about the bounding from below. (I know... i had a rough day)
    But still I'm confused about the induction hypothesis :S
    Normally, inductions are all about a base case ( m=0?) and an inductive step (do we need to show for 2^{(m+1)+1}?)
    I'm really confused! Thank you!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1

    Re: Proof that a sum is bounded by given functions?

    Quote Originally Posted by Flexdec View Post
     H_N = \sum_{i=1}^N\frac{1}{i}
    Given the special case where
     N = 2^{m+1}
    I have to prove that H_N is logarithmically bounded by
     1+\frac{\lg{N}}{2} \leq H_{N} \leq 1+\lg{N}
    Quote Originally Posted by Flexdec View Post
    I kinda guessed it was by induction but didn't think about the bounding from below. (I know... i had a rough day) But still I'm confused about the induction hypothesis :S
    Normally, inductions are all about a base case ( m=0?) and an inductive step (do we need to show for 2^{(m+1)+1}?)
    Actually the is very well know similar inequality:
    H_n-1\le\log(n)\le H_{n-1}.
    That gives you very quickly the RHS.

    But I admit that I have not seen the LHS bound. So perhaps induction is the best approach.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,501
    Thanks
    765

    Re: Proof that a sum is bounded by given functions?

    Quote Originally Posted by Flexdec View Post
    But still I'm confused about the induction hypothesis :S
    Normally, inductions are all about a base case ( m=0?) and an inductive step (do we need to show for 2^{(m+1)+1}?)
    Yes.

    To be more explicit, prove P(m) for all m\ge 0 by induction on m where P(m) is 1+\frac{m+1}{2} \leq H_{2^{m+1}}\leq m+2 .

    In the induction step, when you are proving P(m+1) from P(m), you know the lower and upper bounds on H_{2^{m+1}}. Also, it is easy to get lower and upper bounds on H_{2^{m+2}}-H_{2^{m+1}} by replacing the tail of the sum H_{2^{m+2}} with its smallest or biggest term, respectively.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jun 2013
    From
    montreal
    Posts
    10

    Re: Proof that a sum is bounded by given functions?

    Ok so i give it a try. Given the special case  N = 2^{m+1} , the sum is given by

    H_{2^{m+1}} = \sum_{i=2^m+1}^{2^{m+1}}\frac{1}{i}

    Lets prove, by induction, the following logarithmic bounds

    1+\frac{\lg(2^{m+1})}{2} \leq H_{2^{m+1}} \leq 1+\lg(2^{m+1})\linebreak\Rightarrow1+\frac{m+1}{2}  \leq\frac{1}{1}+...+\frac{1}{2^{m+1}}\leq m+2

    *edited ^

    First, lets start with the base case  m=0

    ????  1+\frac{1}{2} \leq \frac{1}{2}+...+\frac{1}{2} \leq 2 ????

    well from there I get stuck, I think I did something wrong ...

    Thank you for your help so far!!
    Last edited by Flexdec; June 4th 2013 at 06:08 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,501
    Thanks
    765

    Re: Proof that a sum is bounded by given functions?

    Quote Originally Posted by Flexdec View Post
    Given the special case  N = 2^{m+1} , the sum is given by

    H_{2^{m+1}} = \sum_{i=2^m+1}^{2^{m+1}}\frac{1}{i}

    Lets prove, by induction, the following logarithmic bounds

    1+\frac{\lg(2^{m+1})}{2} \leq H_{2^{m+1}} \leq 1+\lg(2^{m+1})\linebreak\Rightarrow1+\frac{m+1}{2} \leq \frac{1}{2^m+1}+...+\frac{1}{2^{m+1}} \leq m+2
    Why did you replace H_{2^{m+1}} with \frac{1}{2^m+1}+...+\frac{1}{2^{m+1}}? The sum H_{2^{m+1}} starts with 1.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Jun 2013
    From
    montreal
    Posts
    10

    Re: Proof that a sum is bounded by given functions?

    I guess the hint messed with my head :P

    So for base case it would be

    1+\frac{1}{2}\leq1+\frac{1}{2}\leq2

    right?
    Last edited by Flexdec; June 4th 2013 at 06:06 AM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,501
    Thanks
    765

    Re: Proof that a sum is bounded by given functions?

    Quote Originally Posted by Flexdec View Post
    So for base case it would be

    1+\frac{1}{2}\leq1+\frac{1}{2}\leq2

    right?
    Yes.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Jun 2013
    From
    montreal
    Posts
    10

    Re: Proof that a sum is bounded by given functions?

    and from there...

    2+\frac{m}{2}\leq ??? \leq m+3

    I'm lost :S
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,501
    Thanks
    765

    Re: Proof that a sum is bounded by given functions?

    Look again at post #5. You assume the induction hypothesis P(m), i.e., 1+\frac{m+1}{2} \leq H_{2^{m+1}}\leq m+2 . From this assumption, you need to prove P(m+1), i.e., 1+\frac{m+2}{2} \leq H_{2^{m+2}}\leq m+3 . Now, H_{2^{m+2}}=H_{2^{m+1}}+\frac{1}{2^{m+1}+1}+\dots+  \frac{1}{2^{m+2}}. The induction hypothesis gives you an upper and a lower bound on the first term of this sum, i.e., H_{2^{m+1}}. As for the tail of H_{2^{m+2}}, replace all 2^{m+1} terms with the smallest term \frac{1}{2^{m+2}} to get a lower bound and with the largest term \frac{1}{2^{m+1}+1} to get an upper bound. By adding the obtained lower bounds on H_{2^{m+1}} and the tail you get a lower bound on H_{2^{m+2}}, and by adding the obtained upper bounds on H_{2^{m+1}} and the tail, you get an upper bound on H_{2^{m+2}}. The two resulting inequalities are precisely P(m+1).
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Jun 2013
    From
    montreal
    Posts
    10

    Re: Proof that a sum is bounded by given functions?

    What do you mean by tail, all the terms except the first?
    thanks!
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,501
    Thanks
    765

    Re: Proof that a sum is bounded by given functions?

    Quote Originally Posted by Flexdec View Post
    What do you mean by tail, all the terms except the first?
    Yes, by the "tail of H_{2^{m+2}}" I refer to \frac{1}{2^{m+1}+1}+\dots+  \frac{1}{2^{m+2}}.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Newbie
    Joined
    Jun 2013
    From
    montreal
    Posts
    10

    Re: Proof that a sum is bounded by given functions?

    And one last thing!!!

    when you say replace all 2^{m+1} terms you mean replacing all the terms of the tail right?
    I can't figure out how it can equal the lower and upper bounds when added to H_{2^{m+1}} bounds.
    For example, for lower bound:
    1+\frac{m+1}{2}+T=1+\frac{m+2}{2}
    where T is the modified tail you're talking about. would T be like
    \frac{1}{2^{m+2}}+...+\frac{1}{2^{m+2}}
    this is what I understood..
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,501
    Thanks
    765

    Re: Proof that a sum is bounded by given functions?

    Quote Originally Posted by Flexdec View Post
    when you say replace all 2^{m+1} terms you mean replacing all the terms of the tail right?
    Yes, there are exactly 2^{m+1} in the tail of H_{2^{m+2}}.

    Quote Originally Posted by Flexdec View Post
    I can't figure out how it can equal the lower and upper bounds when added to H_{2^{m+1}} bounds.
    For example, for lower bound:
    1+\frac{m+1}{2}+T=1+\frac{m+2}{2}
    where T is the modified tail you're talking about. would T be like
    \frac{1}{2^{m+2}}+...+\frac{1}{2^{m+2}}
    You are correct. When we replace all 2^{m+1} terms with the smallest term \frac{1}{2^{m+2}}, we get 2^{m+1}\cdot\frac{1}{2^{m+2}}=\frac12, and 1+\frac{m+1}{2}+\frac12=1+\frac{m+2}{2}.

    For the upper bound, we won't get the exact equality, but if we replace all 2^{m+1} terms with the largest term \frac{1}{2^{m+1}+1} and add the upper bound of H_{2^{m+1}}, i.e., m + 2, we get something that is ≤ (rather than =) the required upper bound m + 3.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: October 21st 2012, 01:16 PM
  2. Bounded functions ..
    Posted in the Calculus Forum
    Replies: 3
    Last Post: December 29th 2010, 01:27 PM
  3. Bounded functions
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: March 18th 2010, 07:17 AM
  4. Replies: 2
    Last Post: October 19th 2009, 01:17 PM
  5. Bounded functions
    Posted in the Calculus Forum
    Replies: 3
    Last Post: October 21st 2008, 06:55 PM

Search Tags


/mathhelpforum @mathhelpforum