If $f:\mathbb{R}\to\mathbb{R}$ is continuous and monotonically increasing on the interval $[1,\infty]$ with $f'(x)\leq\frac{1}{x}$ on the interval $[1,\infty]$ then is it true that:

$$\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 experimenting with sums of the natural logarithm. It makes intuitive sense to me, because any monotonic function $f(x)$ with a derivative that isn't monotonic results in that function increasing 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 $\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.

  • 2
    $\begingroup$ 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$? $\endgroup$ – joriki Dec 23 '12 at 20:25
  • $\begingroup$ What about $f(x) = 1/x$? As joriki says, maybe you want monotonically increasing? This also seems needed for $\sum f(k) < nf(n)$. $\endgroup$ – ronno Dec 23 '12 at 20:29
  • $\begingroup$ @joriki: You are definitely right, that was me misreading the question! I'll remove my comment $\endgroup$ – 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 $$

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

  • $\begingroup$ 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. $\endgroup$ – robjohn Dec 23 '12 at 21:26
  • $\begingroup$ @robjohn: Strange, my answer is essentially the same as yours except I left out some details. $\endgroup$ – Eric Naslund Dec 23 '12 at 21:45
  • $\begingroup$ Indeed (+1). $\sum\limits_{k=1}^{n}\left(\log\left(\frac{n}{k}\right)+C\right)=O(n)$ is true, but not immediately evident. $\endgroup$ – robjohn Dec 23 '12 at 21:46

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.