Strictly increasing function $f: \mathbb{N} \to \mathbb{R}^+$ such that $\lim\limits_{n \to \infty} \frac{f(n)}{n} = 0$ and $f(n)+f(3n) \ge 2f(2n).$

Question

Does there exist a strictly increasing function $f: \mathbb{N} \to \mathbb{R}^+$ such that $\lim\limits_{n \to \infty} \frac{f(n)}{n} = 0$ and $f(n)+f(3n) \ge 2f(2n)$ for all sufficiently large $n$?

The reason I am asking is that the existence of such a function would give me a nice counterexample to a claim I'm investigating that might be false. The actual claim itself is very broad and appears too good to be true, but this question is concise and specific, so I decided to focus on it. Trying to construct such a function using a greedy algorithm fails epically. You get something that's sort of an arithmetic series, which grows too quickly to satisfy the limit condition.

Let $d=f(2)-f(1).$ Then $$f(24)-f(16) \ge f(16)-f(8) \ge f(15)-f(10) \ge f(10)-f(5) \ge f(9)-f(6) \ge f(6)-f(3) \ge f(6)-f(4) \ge f(4)-f(2) \ge f(3)-f(2) \ge d,$$ so $f(24) \ge 5d.$ Continuing this process gives you $f(3F_{n+1}) \ge nd$ and you don't miss many numbers (we dropped down from $16 \to 15, 10 \to 9, 4 \to 3$), so perhaps there is an explicit construction involving Fibonacci numbers.

Answer 1

The inequality makes this function convex on the natural numbers, and since you need a strictly increasing function, you cannot do so such that it is bound above by $f(n) = n$. Since for sufficiently large $n$, we can consider $f$ to be convex in a sense. Suppose we use straight line segments to join the function points at natural numbers, the slope of these lines will continuously increase as $n$ grows larger

$$f(3n)-f(2n) > f(2n)-f(n)$$

Hence, it is inevitable that the function will cross $f(n) = n$, meaning that you cannot have $\lim_{n \to \infty}\frac{f(n)}{n} = 0$

Answer 2

You cannot find such a function. Credits to Robert Israel for the idea.

Let $\alpha > 0.$ Since $f(n)-\alpha n = n\left(\frac{f(n)}{n}-\alpha\right)$ and $\frac{f(n)}{n}-\alpha \to -\alpha$ as $n \to \infty,$ we have $f(n)-\alpha n \to -\infty$ as $n \to \infty.$

Take $\alpha$ so $f(N) - N \alpha > f(x) - x\alpha$ for all $x < N$, i.e. $$\alpha < \min_{x < N} \frac{f(N) - f(x)}{N-x}.$$ Then the maximum of $f(x) - \alpha x$ for all $x \in \mathbb N$ is attained at some $x_0$ with $x_0 \ge N$. Moreover by choosing $\alpha$ appropriately we can ensure this maximum is unique (because there are only countably many $\alpha$ for which there is a tie).

If $x_0$ is odd, change $\alpha$ so that the maximum occurs at an even number. So suppose $x_0 = 2m.$

Adding $f(2m)-2m\alpha > f(m) - m\alpha$ and $f(2m) - 2\alpha m > f(3m) - 3\alpha m,$ we get $2f(2m) > f(m) + f(3m),$ contradiction.