Function that grows as fast as sum of previous values

118 Views Asked by At

Does there exist a strictly positive, monotonically increasing function $f : \mathbb{N} \to \mathbb{R}$ such that $$ \lim_{n \to \infty} \sum_{k = 1}^n \frac{f(k)}{f(n)} = 1 $$ My guess is that there shouldn't exist such a function, but I haven't been able to prove it.

1

There are 1 best solutions below

3
On BEST ANSWER

In the sum, $k$ may be equal to $n$, so we must have $$\lim_{n\to\infty}\frac{\sum_{k=1}^{n-1}f(k)}{f(n)}+1=1$$ $$\lim_{n\to\infty}\frac{\sum_{k=1}^{n-1}f(k)}{f(n)}=0$$ The factorial numbers nicely satisfy this relation: set $f(n)=n!$, and notice that for $n>2$, $\frac{\sum_{k=1}^{n-1}k!}{n!}<\frac2n$, so the desired limit is satisfied.


If $f(n)$ is not included in the summation, $2^n$ will suffice, as pointed out by Mees de Vries in the question comments.