Let f(x) = 1 + 1/2 + 1/3 + ... + 1/[(2^n)-1]

Date: 05/15/99 at 05:45:07
From: Anoop Manghat
Subject: Inequality

Respected sir,

This is a question from the recent IIt entrance examination that I 
took.

Let f(x)= 1 + 1/2 + 1/3 + ... + 1/[(2^n)-1]
Then which of the follwing is/are correct?
1. f(100) < or = 100
2. f(100) > 100
3. f(200) < or = 200
4. f(200) > 100

Thanking you,
Anoop

Date: 05/15/99 at 11:45:16
From: Doctor Kate
Subject: Re: Inequality

Anoop,

Since they are not asking for you to find f(100) or f(200), let's not 
do that (it could take a long time, anyway). Let's try to use some 
common sense approaches, so we won't need a calculator.

You may have learned from class that a series like this can be 
approximated by the definite integral from 1 to 2^100 - 1 of 1/x dx.  
Draw a smooth curve joining the points (x, 1/x) on a graph - that's 
the graph of 1/x. Now draw a "bar graph" or a "staircase" where each 
step is at level 1/x at each integer x. The area under these two 
graphs will be about the same (since one is just a little more jagged 
than the other). And the area under the second one is simply the sum 
as given to you above. Since each "step" has width 1, and height 1/x, 
f(n) = 1 + 1/2 + 1/3 + ... up to 1/[(2^n)-1] is the area under the 
staircase from 1 to 2^n - 1. That's an intuitive picture of why you 
can use an integral to solve this question. If you are not expected to 
know a bit of integral calculus for your examination, write back to 
us, restating your question, and asking for a calculusless solution, 
and we'll give it a try.

Since the integral of 1/x is ln(x), this is ln (2^100 - 1). If you ask 
a powerful calculator, it can calculate this for you. However, you may 
not have had a calculator, so then what?

Well, ln(2^100 - 1) will be very close to ln(2^100), and then we use 
some logarithm rules to find

ln(2^100) = 100 * ln(2)

And ln(2) is less than 1 (since 2 is less than e = 2.718..., so the 
power to which we would have to raise e would be less than 1 in order 
to get 2 as a result).

So f(100) is probably < 100. We have used some approximation, but it's 
a good guess, considering we don't want to work it all out.

Now what about 200? We use the same process, and find the same result 
- it will be less than 200 - you give this one a try.

The series they gave you, 1 + 1/2 + 1/3 + 1/4 + ..., if you were to 
add up far enough out, would eventually be bigger than any number you 
want, that is to say, it "diverges," but it is very very slow to grow, 
so you can add up an awful lot of terms (more than 2^100) before you 
even hit 100. Imagine how long it would take to get to 1000 or ten 
million ... but you could eventually do it! I like this series - it's 
an amazing thing.

- Doctor Kate, The Math Forum
  http://mathforum.org/dr.math/