TITLE: How to prove that superadditive function has this property?
QUESTION [9 upvotes]: Let $f: [0, \infty) \to \mathbb R$ be a function satisfying the following conditions:

For any $x,y \ge 0$, $f(x+y) \ge f(x) + f(y)$.
For any $x \in [0,2]$, $f(x) \ge x^2 - x$.

Prove that, for any positive integer $M$ and positive reals $n_1,\dots,n_M$ with $n_1+\dots+n_M = M$, we have
$$f(n_1)+\dots+f(n_M) \ge 0$$
How can I prove this statement?

REPLY [1 votes]: First, note that for a nonnegative integer $N$ and nonnegative $x$, we have $f(Nx)\ge Nf(x)$. Now if for each integer $i$ such that $1\le i\le M$, we let $m_i=\big\lfloor\frac{n_i}{2}\big\rfloor$ and $\epsilon_i=n_i-2m_i$ then:
$$f(n_1)+\dots+f(n_M)=f(2m_1+\epsilon_1)+\dots+f(2m_1+\epsilon_1)\\
\ge f(2m_1)+\dots+f(2m_M)+f(\epsilon_1)+\dots+f(\epsilon_M)$$
Because each $m_i$ is a nonnegative integer and for each $\epsilon_i$ we have $0\le\epsilon_i\leq2$, therefore:
$$f(2m_1)+\dots+f(2m_M)+f(\epsilon_1)+\dots+f(\epsilon_M)\\
\ge m_1f(2)+\dots+m_Mf(2)+\big(\epsilon_1^2-\epsilon_1\big)+\dots+\big(\epsilon_M^2-\epsilon_M\big)\\
\ge2m_1+\dots+2m_M+(\epsilon_1^2-\epsilon_1)+\dots+(\epsilon_M^2-\epsilon_M)\\
=(2m_1+\epsilon_1)+\dots+(2m_M+\epsilon_M)+\big(\epsilon_1^2-2\epsilon_1\big)+\dots+\big(\epsilon_M^2-2\epsilon_M\big)\\
\ge n_1+\dots+n_M+(-1)+\dots+(-1)\\
=M-M=0\\$$
So we conclude that $f(n_1)+\dots+f(n_M)\geq0$. It's easy to see that if the equality holds, then each $\epsilon_i$ must be equal to $1$. Because
$n_1+\dots+n_M=M$, therefore each $n_i$ must be equal to $1$ and also $f(1)$ must be equal to $0$. Obviously, the converse is also true.
{"set_name": "stack_exchange", "score": 9, "question_id": 721108}