6
$\begingroup$

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

  • 0
    @joriki: You are defini$t$ely righ$t$, $t$hat was me misreading the question! I'll remove my comment2012-12-23

2 Answers 2

5

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 $

  • 0
    @MikeSpivey: True. Here the $\log$ growth is given by $f'(x)\le1/x$.2012-12-23
2

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.

  • 0
    Indeed (+1). $\sum\limits_{k=1}^{n}\left(\log\left(\frac{n}{k}\right)+C\right)=O(n)$ is true, but not immediately evident.2012-12-23