6
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Hint: $\ln(n)-\ln(n-1)=\int_{n-1}^n \frac{1}{x}\,dx$. $\endgroup$ – Pocho la pantera Sep 20 '13 at 16:48
  • 1
    $\begingroup$ 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. $\endgroup$ – imranfat Sep 20 '13 at 16:52
  • $\begingroup$ I've just extended my answer by adding a proof of boundedness. $\endgroup$ – Michael Hardy Sep 21 '13 at 18:06
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I don't understand step (1) and (2), is (1) is my $a_n$? it doesn't look exactly the same $\endgroup$ – Diane Vanderwaif Sep 21 '13 at 13:35
  • $\begingroup$ 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. $\endgroup$ – Michael Hardy Sep 21 '13 at 17:54
  • $\begingroup$ I just fixed an error: it should be $\displaystyle\int_n^{n+1}$, not $\displaystyle\int_{n-1}^n$. ${}\qquad{}$ $\endgroup$ – Michael Hardy Sep 21 '13 at 17:58
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.