# Currious property of monotonic functions

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.

-
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

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

-
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

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.

-
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