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

$\endgroup$
3
  • 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, 2012 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, 2012 at 20:29
  • $\begingroup$ @joriki: You are definitely right, that was me misreading the question! I'll remove my comment $\endgroup$ Dec 23, 2012 at 21:04

2 Answers 2

5
$\begingroup$

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

$\endgroup$
3
  • $\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, 2012 at 21:22
  • $\begingroup$ Interesting. My answer here comes to similar conclusions on a related question. $\endgroup$ Dec 23, 2012 at 21:52
  • $\begingroup$ @MikeSpivey: True. Here the $\log$ growth is given by $f'(x)\le1/x$. $\endgroup$
    – robjohn
    Dec 23, 2012 at 22:12
2
$\begingroup$

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.

$\endgroup$
3
  • $\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, 2012 at 21:26
  • $\begingroup$ @robjohn: Strange, my answer is essentially the same as yours except I left out some details. $\endgroup$ Dec 23, 2012 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, 2012 at 21:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .