# Proof that a sum is bounded by given functions?

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Jun 3rd 2013, 01:08 PM
Flexdec
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

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

Given the special case where

$\displaystyle N = 2^{m+1}$

I have to prove that $\displaystyle H_N$ is logarithmically bounded by

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

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

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

in $\displaystyle 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!
• Jun 3rd 2013, 01:50 PM
emakarov
Re: Proof that a sum is bounded by given functions?
Prove the required claim by induction on m. This requires bounding $\displaystyle \sum_{i=2^m+1}^{2^{m+1}}1/i$ from below and from above, as per the hint.
• Jun 3rd 2013, 05:10 PM
Flexdec
Re: Proof that a sum is bounded by given functions?

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 ($\displaystyle m=0?$) and an inductive step (do we need to show for $\displaystyle 2^{(m+1)+1}$?)
I'm really confused! Thank you!
• Jun 3rd 2013, 05:50 PM
Plato
Re: Proof that a sum is bounded by given functions?
Quote:

Originally Posted by Flexdec
$\displaystyle H_N = \sum_{i=1}^N\frac{1}{i}$
Given the special case where
$\displaystyle N = 2^{m+1}$
I have to prove that $\displaystyle H_N$ is logarithmically bounded by
$\displaystyle 1+\frac{\lg{N}}{2} \leq H_{N} \leq 1+\lg{N}$

Quote:

Originally Posted by Flexdec
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 ($\displaystyle m=0?$) and an inductive step (do we need to show for $\displaystyle 2^{(m+1)+1}$?)

Actually the is very well know similar inequality:
$\displaystyle 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.
• Jun 4th 2013, 04:15 AM
emakarov
Re: Proof that a sum is bounded by given functions?
Quote:

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

Yes.

To be more explicit, prove P(m) for all $\displaystyle m\ge 0$ by induction on m where P(m) is $\displaystyle 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 $\displaystyle H_{2^{m+1}}$. Also, it is easy to get lower and upper bounds on $\displaystyle H_{2^{m+2}}-H_{2^{m+1}}$ by replacing the tail of the sum $\displaystyle H_{2^{m+2}}$ with its smallest or biggest term, respectively.
• Jun 4th 2013, 05:45 AM
Flexdec
Re: Proof that a sum is bounded by given functions?
Ok so i give it a try. Given the special case $\displaystyle N = 2^{m+1}$, the sum is given by

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

Lets prove, by induction, the following logarithmic bounds

$\displaystyle 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 $\displaystyle m=0$

???? $\displaystyle 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!!
• Jun 4th 2013, 05:59 AM
emakarov
Re: Proof that a sum is bounded by given functions?
Quote:

Originally Posted by Flexdec
Given the special case $\displaystyle N = 2^{m+1}$, the sum is given by

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

Lets prove, by induction, the following logarithmic bounds

$\displaystyle 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 $\displaystyle H_{2^{m+1}}$ with $\displaystyle \frac{1}{2^m+1}+...+\frac{1}{2^{m+1}}$? The sum $\displaystyle H_{2^{m+1}}$ starts with 1.
• Jun 4th 2013, 06:03 AM
Flexdec
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

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

right?
• Jun 4th 2013, 06:12 AM
emakarov
Re: Proof that a sum is bounded by given functions?
Quote:

Originally Posted by Flexdec
So for base case it would be

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

right?

Yes.
• Jun 4th 2013, 06:15 AM
Flexdec
Re: Proof that a sum is bounded by given functions?
and from there...

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

I'm lost :S
• Jun 4th 2013, 09:46 AM
emakarov
Re: Proof that a sum is bounded by given functions?
Look again at post #5. You assume the induction hypothesis P(m), i.e., $\displaystyle 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., $\displaystyle 1+\frac{m+2}{2} \leq H_{2^{m+2}}\leq m+3$. Now, $\displaystyle 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., $\displaystyle H_{2^{m+1}}$. As for the tail of $\displaystyle H_{2^{m+2}}$, replace all $\displaystyle 2^{m+1}$ terms with the smallest term $\displaystyle \frac{1}{2^{m+2}}$ to get a lower bound and with the largest term $\displaystyle \frac{1}{2^{m+1}+1}$ to get an upper bound. By adding the obtained lower bounds on $\displaystyle H_{2^{m+1}}$ and the tail you get a lower bound on $\displaystyle H_{2^{m+2}}$, and by adding the obtained upper bounds on $\displaystyle H_{2^{m+1}}$ and the tail, you get an upper bound on $\displaystyle H_{2^{m+2}}$. The two resulting inequalities are precisely P(m+1).
• Jun 4th 2013, 12:01 PM
Flexdec
Re: Proof that a sum is bounded by given functions?
What do you mean by tail, all the terms except the first?
thanks!
• Jun 4th 2013, 12:16 PM
emakarov
Re: Proof that a sum is bounded by given functions?
Quote:

Originally Posted by Flexdec
What do you mean by tail, all the terms except the first?

Yes, by the "tail of $\displaystyle H_{2^{m+2}}$" I refer to $\displaystyle \frac{1}{2^{m+1}+1}+\dots+ \frac{1}{2^{m+2}}$.
• Jun 4th 2013, 12:34 PM
Flexdec
Re: Proof that a sum is bounded by given functions?
And one last thing!!!

when you say replace all $\displaystyle 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 $\displaystyle H_{2^{m+1}}$ bounds.
For example, for lower bound:
$\displaystyle 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
$\displaystyle \frac{1}{2^{m+2}}+...+\frac{1}{2^{m+2}}$
this is what I understood..
• Jun 4th 2013, 01:04 PM
emakarov
Re: Proof that a sum is bounded by given functions?
Quote:

Originally Posted by Flexdec
when you say replace all $\displaystyle 2^{m+1}$ terms you mean replacing all the terms of the tail right?

Yes, there are exactly $\displaystyle 2^{m+1}$ in the tail of $\displaystyle H_{2^{m+2}}$.

Quote:

Originally Posted by Flexdec
I can't figure out how it can equal the lower and upper bounds when added to $\displaystyle H_{2^{m+1}}$ bounds.
For example, for lower bound:
$\displaystyle 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
$\displaystyle \frac{1}{2^{m+2}}+...+\frac{1}{2^{m+2}}$

You are correct. When we replace all $\displaystyle 2^{m+1}$ terms with the smallest term $\displaystyle \frac{1}{2^{m+2}}$, we get $\displaystyle 2^{m+1}\cdot\frac{1}{2^{m+2}}=\frac12$, and $\displaystyle 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 $\displaystyle 2^{m+1}$ terms with the largest term $\displaystyle \frac{1}{2^{m+1}+1}$ and add the upper bound of $\displaystyle H_{2^{m+1}}$, i.e., m + 2, we get something that is ≤ (rather than =) the required upper bound m + 3.
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last