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.

If $f(x)$ is continuous and monontonicly increaseing on the interval $[1,\infty]$, and $f'(x)\leq\frac{1}{x}$ on the interval $[1,\infty]$,

is $$\lim_{n \rightarrow \infty} \frac{1}{nf(n)}\sum_{k=1}^n f(k)=1$$

This is by no means a theorem also, its just a guess I made after expeirmenting with sums of the natural logarithm. It makes intuitive sense to me, because any monotonic function $f(x)$ with a derivertive that isn't monotonic results in that function increaseing as x increases, but the rate at which it increases is decreasing, therefore in a sense its sort of approaching a constant value, ie 'increaseing at a very slow rate', making all terms slightly less then $f(x)$ , ie $f(x-1), f(x-2),\ldots$ etc, all very close in value to $f(x)$. Meaning the summands towards the end of the summation should all be very close in value, while the smaller ones like $f(1),f(2),\ldots$ etc are neglible.

So athough clearly from the definition $\sum_{k=1}^n f(k)<nf(n)$, I still find it reasonable that $\lim_{n \rightarrow \infty} \frac{1}{nf(n)}\sum_{k=1}^n f(k)=1$

A disproof/proof of the theorem would be nice, but in addition some background intuition would also be greatly appreciated.

share|improve this question
2  
It seems your conditions don't exclude e.g. $f(x)=-x^2$. Perhaps you intended $f$ to be monotonically increasing, or $|f'(x)|\le1/x$? –  joriki Dec 23 '12 at 20:25
    
What about $f(x) = 1/x$? As joriki says, maybe you want monotonically increasing? This also seems needed for $\sum f(k) < nf(n)$. –  ronno Dec 23 '12 at 20:29
    
@joriki: You are definitely right, that was me misreading the question! I'll remove my comment –  Eric Naslund Dec 23 '12 at 21:04
add comment

2 Answers

up vote 4 down vote accepted

If $f$ is non-decreasing, $$ \sum_{k=1}^nf(k)\le nf(n) $$ Since $0\le f'(x)\le1/x$, we have for $k\le n$ $$ f(n)-f(k)\le \log(n)-\log(k) $$ Therefore, for $n\ge1$, $$ \begin{align} \sum_{k=1}^nf(k) &\ge\sum_{k=1}^n{\large(}f(n)-\log(n)+\log(k){\large)}\\ &=nf(n)-n\log(n)+\sum_{k=1}^n\log(k)\\ &\ge nf(n)-n\log(n)+\int_1^n\log(x)\,\mathrm{d}x\\[6pt] &=nf(n)-n\log(n)+n\log(n)-n+1\\[12pt] &=nf(n)-n+1 \end{align} $$ So we have for $n\ge1$, $$ nf(n)-n+1\le\sum_{k=1}^nf(k)\le nf(n) $$ Thus, if $\lim\limits_{n\to\infty}f(n)=\infty$, we have $$ \sum_{k=1}^nf(k)\sim nf(n) $$ However, if $\lim\limits_{n\to\infty}f(n)=L$, then for any $\epsilon>0$, there is an $N$ so that if $n\gt N$, then $$ L-\epsilon\le f(n)\le L $$ Then, for $n\gt N$, $$ \begin{align} \sum_{k=1}^nf(k) &\ge\sum_{k=1}^Nf(k)+\sum_{k=N+1}^nL-\epsilon\\ &=\sum_{k=1}^Nf(k)+(n-N)(L-\epsilon)\\ &\ge\sum_{k=1}^Nf(k)+n(f(n)-\epsilon)-N(L-\epsilon)\\ &=n(f(n)-\epsilon)+\left(\sum_{k=1}^Nf(k)-N(L-\epsilon)\right) \end{align} $$ Since $\epsilon$ was arbitrary, we have, if $\lim\limits_{n\to\infty}f(n)=L$, $$ \sum_{k=1}^nf(k)\sim nf(n) $$ Faster growth:

Suppose that $f'(x)=1/x^\alpha$, where $\alpha<1$; e.g. $f(x)=\frac1{1-\alpha}x^{1-\alpha}$. Then the Euler-Maclaurin Sum Formula says $$ \sum_{k=1}^nf(n)=\frac1{(1-\alpha)(2-\alpha)}n^{2-\alpha}+O\left(n^{1-\alpha}\right) $$ which means that $$ \frac1{nf(n)}\sum_{k=1}^nf(n)=\frac1{2-\alpha}+O\left(1/n\right) $$ Therefore, $$ \lim_{n\to\infty}\frac1{nf(n)}\sum_{k=1}^nf(n)=\frac1{2-\alpha}<1 $$

share|improve this answer
    
This is the answer I posted to a previous incarnation of this question (since rolled back to a completely different question). –  robjohn Dec 23 '12 at 21:22
    
Interesting. My answer here comes to similar conclusions on a related question. –  Mike Spivey Dec 23 '12 at 21:52
    
@MikeSpivey: True. Here the $\log$ growth is given by $f'(x)\le1/x$. –  robjohn Dec 23 '12 at 22:12
add comment

Your conjecture is true for monotonic $f:[1,\infty)\rightarrow[a,\infty)$ for any $a>0$ and in this case the limit equals $1$. To prove this, I will show that $$\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{k=1}^{n}\frac{\left(f(n)-f(k)\right)}{f(n)}=0.\ \ \ \ \ \ \ \ \ \ \ (1)$$ There are two cases, either $f$ is unbounded and $\lim_{n\rightarrow\infty}f(n)=\infty,$ or it is bounded and $\lim_{n\rightarrow\infty}f(n)=c.$ (Recall that bounded monotonic sequences converge)

Case 1: The derivative condition tells us that for an integer $A$

$$f(n)-f(A)\leq\sum_{k=A}^{n}\frac{1}{k}\leq\log\left(\frac{n}{A}\right)+C$$ and so $$\sum_{k=1}^{n}f(n)-f(k)\leq\sum_{k=1}^{n}\left(\log\left(\frac{n}{k}\right)+C\right)=O(n).$$ Thus, $$\frac{1}{nf(n)}\sum_{k=1}^{n}\left(f(n)-f(k)\right)=O\left(\frac{1}{f(n)}\right),$$ and since $f(n)\rightarrow\infty,$ the limit is $0$.

Case 2:

When $f$ has a positive limit, equation $(1)$ is equivalent to $$\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{k=1}^{n}\left(f(n)-c\right)=0.$$ To prove this, let $\epsilon>0.$ Since $f$ has a limit, there exists $N(\epsilon)$ such that for all $n>N,$ $|f(n)-c|\leq\epsilon.$ This implies that $$\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{k=1}^{n}|f(n)-c|\leq\epsilon.$$ Since this holds for every $\epsilon>0,$ it follows that the limit equals $0$.

Remark: Note that the conjecture is not true for $f:[1,\infty)\rightarrow[0,\infty)$ as $f(x)=\frac{1}{x}$ provides a counter example.

share|improve this answer
    
On the previous incarnation of this question, I asked whether $f$ was monotonically increasing, and I mentioned that it was not necessarily true if $f$ were monotonically decreasing. I see that "increasing" has been added to the question. –  robjohn Dec 23 '12 at 21:26
    
@robjohn: Strange, my answer is essentially the same as yours except I left out some details. –  Eric Naslund Dec 23 '12 at 21:45
    
Indeed (+1). $\sum\limits_{k=1}^{n}\left(\log\left(\frac{n}{k}\right)+C\right)=O(n)$ is true, but not immediately evident. –  robjohn Dec 23 '12 at 21:46
add comment

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.