Increasing and bounded sequence proof

Prove that the sequence $a_n= 1+ \frac 12+ \frac 13+\cdots+ \frac 1n-\ln(⁡n)$ is increasing and bounded above. Conclude that it’s convergent.

This what I got so far

Proof:

Part 1: Proving $a_n$ is increasing by induction.

Base: $a_1=1$

$a_2=1+\frac 12= \frac 32$

$a_1≤a_2$

So the base case is established.

Induction step: We assume that $a_{n-1}≤a_n$. We will show that $a_n≤a_{n+1}$. Since

$a_{n-1}≤a_n$

$$1+ \frac 12+ \frac 13+\cdots+ \frac{1}{(n-1)}-\ln(n-1) \leq 1+ \frac 12+ \frac 13+\cdots+ \frac 1n-\ln n$$

How should I continue?

• Hint: $\ln(n)-\ln(n-1)=\int_{n-1}^n \frac{1}{x}\,dx$. – Pocho la pantera Sep 20 '13 at 16:48
• In reference to Pocho, make a drawing of the function y=1/x and draw rectangles with base 1 and the width as y-values on top of it. Look at the difference of the area of each rectangle and the area under the curve passing through that rectangle. – imranfat Sep 20 '13 at 16:52
• I've just extended my answer by adding a proof of boundedness. – Michael Hardy Sep 21 '13 at 18:06

I think you should have been asked to show that $$1+\frac12+\frac13+\cdots+\frac1n-\ln(n+1) \tag 1$$ increases with $n$. The previous term is $$1+\frac12+\frac13+\cdots+\frac{1}{n-1} - \ln n. \tag 2$$ Then the problem is to show that when you subtract $(2)$ from $(1)$, the difference is nonnegative. You get $$\frac1n - \ln(n+1) + \ln n = \int_n^{n+1} \frac1n - \frac1x \, dx. \tag 3$$ It is easy to show that that is nonnegative.

To show that $(1)$ is bounded above, first notice that $(1)$ is equal to the sum of expressions like the one in $(3)$: $$\sum_{k=1}^n \int_k^{k+1} \frac1k - \frac1x\, dx. \tag 4$$ Then $$[\text{expression in (4)}] \ge \sum_{k=1}^n \int_k^{k+1} \frac1k - \frac{1}{k+1}\, dx = \sum_{k=1}^n \frac1k - \frac{1}{k+1},$$ and this is a telescoping sum, and all its terms are non-negative, and it adds up to $1$.

• I don't understand step (1) and (2), is (1) is my $a_n$? it doesn't look exactly the same – Diane Vanderwaif Sep 21 '13 at 13:35
• It's not the same, since it has $n+1$ as the argument to the logarithm where you had $n$. As I said, if you were assigned an exercise asking you to prove that your $a_n$ is increasing, then whoever wrote the exercise probably ought instead to have asked you to show that the sequence in $(1)$ is bounded and increasing. – Michael Hardy Sep 21 '13 at 17:54
• I just fixed an error: it should be $\displaystyle\int_n^{n+1}$, not $\displaystyle\int_{n-1}^n$. ${}\qquad{}$ – Michael Hardy Sep 21 '13 at 17:58

This sequence is NOT increasing and is in fact DECREASING.

Proof:

$$a_n = 1+\frac{1}{2} + \cdots + \frac{1}{n} - \ln(n)$$

$$a_{n+1}=1+\frac{1}{2} + \cdots + \frac{1}{n}+\frac{1}{n+1} - \ln(n+1)$$

so

$$a_{n+1}=a_n + (\ln(n) +\frac{1}{n+1} - \ln(n+1)) = a_n + \frac{1}{n+1} - (\ln(n+1) - \ln(n))$$

$$\ln(n+1)-\ln(n) = \int_n^{n+1}\frac{1}{t}dt > \frac{1}{n+1}$$

To see the last line just draw a graph of $\frac{1}{t}$ between $n$ and $n+1$ and draw a box of width $1$ and height $\frac{1}{n+1}$ (i.e. the box touches $\frac{1}{t}$ at $t=\frac{1}{n+1}$).

NOTE: Your base case was not done properly since you forgot to subtract $\ln(1)$ and $\ln(2)$ (granted $\ln(1) = 0$) if you subtracted $\ln(2) \approx 0.693147 > 0.5$ you would have seen the base case not to hold.

@Patrick's answer shows that the sequence is decreasing. However, we can show boundedness and covergence in a single step since the terms of the sequence are non-negative. I only provide a skeleton solution, which will need fleshing out with a limit argument.

We can begin by rewriting the sequence as: \begin{equation*} \sum_{k=1}^n \frac{1}{k} -\log{n} = \sum_{k=1}^n \frac{1}{k} -\int_{1}^n \frac{1}{x} d{x} = \overbrace{\sum_{k=1}^{n-1} \int_{k}^{k+1} \Bigl( \frac{1}{k} -\frac{1}{x} \Bigr) d{x} +\frac{1}{n}}^\circledast. \end{equation*} The integral's limits provide the inequalities $k\le x \le {k+1}$, with which we obtain the following bounds on the integrand: $$0 \le \frac{1}{k} - \frac{1}{x} \le \frac{1}{k} -\frac{1}{k+1} = \frac{1}{k(k+1)} < \frac{1}{k^2}.$$ Then, after substituting our new integrand $\tfrac{1}{k^2}$, we obtain: \begin{equation*} 0 \le \sum_{k=1}^n \frac{1}{k} -\log{n} =\overbrace{\sum_{k=1}^{n-1} \int_{k}^{k+1} \Bigl( \frac{1}{k} -\frac{1}{x} \Bigr) d{x} +\frac{1}{n}}^\circledast \le \overbrace{\sum_{k=1}^{n-1} \frac{1}{k^2}}^{\spadesuit} +\frac{1}{n}. \end{equation*}

By comparison with the convergent series $\spadesuit$, we find that the original sequence converges.