Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
9  
You are taking the average of things that keep getting smaller so... –  Jonas Teuwen May 2 '11 at 19:06
1  
Maybe you take the difference $f(n)-f(n-1)$ and try to figure out whether it is positive or negative... –  Fabian May 2 '11 at 19:10
1  
@Tim:Do you really want the upper limit on the sum to be $n-1$? –  Chris Leary May 2 '11 at 19:10
    
@Chris: yes, I do. –  Tim May 2 '11 at 19:14
1  
@Tim: Then you take the last term $0$, that doesn't change much about the argument. –  Jonas Teuwen May 2 '11 at 19:24

4 Answers 4

up vote 11 down vote accepted

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$

share|improve this answer
    
Actually for $n=2$ the expression is equal to 0. –  Fabian May 2 '11 at 19:24
    
Thanks Fabian, corrected the mistake –  Shuhao Cao May 2 '11 at 19:26
    
your welcome. +1 nice answer –  Fabian May 2 '11 at 19:31

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

share|improve this answer
    
Nice, simple argument. –  Jonas Teuwen May 2 '11 at 22:25
    
Thanks! Nice indeed. I wish I were able to accept multiple answers. Why isn't it possible on SE sites? –  Tim May 3 '11 at 1:13
    
@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. –  Aryabhata May 3 '11 at 2:13

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

share|improve this answer

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.

share|improve this answer
    
Your calculation doesn't seem to be correct... –  Fabian May 2 '11 at 19:25
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.$$ –  Arturo Magidin May 2 '11 at 19:27
    
What you do with the term $i=n$ in the second sum? –  Fabian May 2 '11 at 19:28
    
I do apologize, I forgot the term "-1". Now I edited the answer and it should be correct. –  Giovanni De Gaetano May 3 '11 at 9:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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