2
$\begingroup$

Define $f: \mathbb{N} \rightarrow \mathbb{R}$ as $f(n)= \frac{1}{n} \sum_{i=1}^{n-1} \frac{1}{i}$.

I was wondering how to tell if $f$ is a increasing or decreasing function?

Thanks and regards!

  • 9
    You are taking the average of things that keep getting smaller so...2011-05-02
  • 1
    Maybe you take the difference $f(n)-f(n-1)$ and try to figure out whether it is positive or negative...2011-05-02
  • 1
    @Tim:Do you really want the upper limit on the sum to be $n-1$?2011-05-02
  • 0
    @Chris: yes, I do.2011-05-02
  • 0
    @Jonas: Not exactly mean.2011-05-02
  • 0
    @Tim: it might be worth calculating $f(1)$, $f(2)$, $f(3)$ and $f(4)$ as it does not appear to be monotonic.2011-05-02
  • 1
    @Tim: Then you take the last term $0$, that doesn't change much about the argument.2011-05-02

4 Answers 4

11

A formal proof would be $$ \begin{align} f(n+1) - f(n) &= \frac{1}{n+1} \sum_{i=1}^{n} \frac{1}{i} - \frac{1}{n} \sum_{i=1}^{n-1} \frac{1}{i} \\ &= \frac{n}{n+1}\frac{1}{n} \left(\sum_{i=1}^{n-1} \frac{1}{i} + \frac{1}{n}\right) - \frac{1}{n} \sum_{i=1}^{n-1} \frac{1}{i} \\ &= (\frac{n}{n+1} - 1)\frac{1}{n} \sum_{i=1}^{n-1} \frac{1}{i} + \frac{1}{n(n+1)} \\ & = \frac{1}{n(n+1)} \left(1 - \sum_{i=1}^{n-1} \frac{1}{i}\right) < 0 \end{align} $$ for $\forall n \geq 3$

  • 0
    Actually for $n=2$ the expression is equal to 0.2011-05-02
  • 0
    Thanks Fabian, corrected the mistake2011-05-02
  • 0
    your welcome. +1 nice answer2011-05-02
7

A simpler proof would be to notice that $\displaystyle f(n) \gt \frac{1}{n}$ (for $n \gt 2$)

Thus $\displaystyle (n+1)f(n+1) - nf(n) = \frac{1}{n} \lt f(n)$ and so $f(n) \gt f(n+1)$.

  • 0
    Nice, simple argument.2011-05-02
  • 0
    Thanks! Nice indeed. I wish I were able to accept multiple answers. Why isn't it possible on SE sites?2011-05-03
  • 0
    @Tim/Jonas: Thanks! @Tim: I guess the intent is to have one answer which will make it easier for people who come across this later. We can always edit the accepted answer to have multiple proofs, I guess.2011-05-03
4

The following 3 condidions are equivalent:

$$f(n)>f(n+1)$$

$$\frac{1+\frac12+\dots+\frac1{n-1}}n>\frac{1+\frac12+\dots+\frac1{n}}{n+1}$$

$$n+\frac{n+1}2+\dots+\frac{n+1}{n-1}+1>n+\frac n2+\dots+\frac n{n-1}+1$$

In the last inequality, the corresponding terms on the LHS are greater (or equal) as the corresponding terms on the RHS. (They both have the same number of terms.) At least one of these inequalities is strict.

EDIT: (From the comments I see that this was not clear enough.)

There is the same number of terms, since I divided $n+1$ (obtained by multypling the first term in the second inequality) between $n$ and $1$ (the first and the last term in the LHS).

0

Consider: $$\begin{align*} n(n+1)(f(n)-f(n+1))&=n(n+1)\left(\frac{1}{n}\sum_{i=1}^{n-1}\frac{1}{i}-\frac{1}{n+1}\sum_{i=1}^{n}\frac{1}{i}\right)\\ &=\sum_{i=1}^{n-1}\left(\frac{n+1}{i}-\frac{n}{i}\right) - 1\\ &=\sum_{i=1}^{n-1}\frac{1}{i} - 1\\ &\geq 0\end{align*}$$ for $n\geq2$.

In specific $f(n)-f(n+1)\geq0$ in general.

Edit: Little writing error.

  • 0
    Your calculation doesn't seem to be correct...2011-05-02
  • 1
    There is a term missing in the secondl ine, since the last sum includes the $n$th term but the first one does not. That is, the second line should be $$\left(\sum_{i=1}^{n-1}\left(\frac{n+1}{i}-\frac{n}{i}\right)\right) - 1.$$2011-05-02
  • 0
    What you do with the term $i=n$ in the second sum?2011-05-02
  • 0
    I do apologize, I forgot the term "-1". Now I edited the answer and it should be correct.2011-05-03