Increasing and bounded sequence proof

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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