# 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$. Commented Sep 20, 2013 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. Commented Sep 20, 2013 at 16:52
• I've just extended my answer by adding a proof of boundedness. Commented Sep 21, 2013 at 18:06

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.

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 Commented Sep 21, 2013 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. Commented Sep 21, 2013 at 17:54
• I just fixed an error: it should be $\displaystyle\int_n^{n+1}$, not $\displaystyle\int_{n-1}^n$. ${}\qquad{}$ Commented Sep 21, 2013 at 17:58

@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.