Expert: Paul Klarreich - 4/28/2009

Question
Hi Paul,  I have had a go at this question but I think my attempt is pretty clumsy and possibly too weak.

Question is:

Show the sequence {a_n} given by a_n = [SUM (r=1 to n)  (1/r) - ln n] is monotone.

My attempt goes along the lines:

using induction, taking n = 1 and n=2, I get a_1 = 1 and a_2 = 0.8069 and thus a_2 - a_1 < 0, therefore it appears to be decreasing.

If i then assume true n = k (k > 0), we have a_k = SUM r=1 to k (1/k) - ln k

And then if you insert n = k+1, you have a_(k+1) = SUM r=1 to k+1 (1/(k+1) - ln (k+1).

a_(k+1) - a_k = 1/(k+1) - ln (k+1) - ln(k), which will be < 0  ##

Thus we have by induction that a_n is strictly decreasing and thus, according to Defn 2.1.8 (given in my unit book), it is monotone.

## I have thought about this since and am not convinced I can jump to the conclusion that this is always < 0

Can you suggest an alternative approach?

Thanks.

Answer
Questioner:   Steve
Country:  Australia
Category:  Advanced Math

Subject:  Monotone sequences
Question:  Hi Paul,  I have had a go at this question but I think my attempt is pretty clumsy and possibly too weak.

Question is:

Show the sequence {a_n} given by a_n = [SUM (r=1 to n)  (1/r) - ln n] is monotone.

My attempt goes along the lines:

using induction, taking n = 1 and n=2, I get a_1 = 1 and a_2 = 0.8069 and thus a_2 - a_1 < 0, therefore it appears to be decreasing.

>> Yes, that appears so.

If i then assume true n = k (k > 0), we have a_k = SUM r=1 to k (1/k) - ln k

And then if you insert n = k+1, you have a_(k+1) = SUM r=1 to k+1 (1/(k+1) - ln (k+1).

a_(k+1) - a_k = 1/(k+1) - ln (k+1) - ln(k), which will be < 0  ##

>> OOPS -- I think you blew a sign here.  I think you want PLUS ln(k)

Thus we have by induction that a_n is strictly decreasing and thus, according to Defn 2.1.8 (given in my unit book), it is monotone.

## I have thought about this since and am not convinced I can jump to the conclusion that this is always < 0

Can you suggest an alternative approach?

Thanks.
...............................

a[k]   =  SUM(j=1 to k)(1/r)  - ln k

a[k+1] =  SUM(j=1 to k+1)(1/r)  - ln (k+1)

a[k+1] - a[k] = 1/(k+1) - ln(k+1) + ln k

a[k+1] - a[k] = 1/(k+1) - (ln(k+1) - ln k)

I think we have the signs right now.

We want to determine whether this is positive or negative.  How about this approach?

ln k = (by definition)

{k
| dt/t
}1

and ln(k+1) = (by definition)

{k+1
| dt/t
}1

So ln (k+1) - ln k is certainly positive and, by rules for adding integrals, is:

{k+1
|   dt/t
}k

Now that is the area under the graph of 1/t from t = k to t = k+1

Now what is 1/(k+1)?
That is the area of the rectangle from t = k to t = k+1 and bounded on top by  y = 1/(k+1), which is a smaller area than the integral.

So

1/(k+1) - (ln(k+1) - ln k)  is smaller minus bigger, so it is negative.  Does that do it?