# How to prove that subadditive function has this property?

Let $f: [0, \infty) \to \Bbb R$ be a function satisfying the following conditions:

(1) For any $x,y \geq 0, f(x+y) \geq f(x) + f(y)$.

(2) For any $x \in [0,2], f(x) \geq 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) \geq 0$$

How can I prove this statement?

## 1 Answer

First, note that for a nonnegative integer $N$ and nonnegative $x$, we have $f(Nx)\geq Nf(x)$. Now if for each integer $i$ such that $1\leq i\leq M$, we let $m_i=\lfloor\frac{n_i}{2}\rfloor$ and $\epsilon_i=n_i-2m_i$ then: $$f(n_1)+\cdots+f(n_M)=f(2m_1+\epsilon_1)+\cdots+f(2m_1+\epsilon_1)\\ \geq f(2m_1)+\cdots+f(2m_M)+f(\epsilon_1)+\cdots+f(\epsilon_M)$$ Because each $m_i$ is a nonnegative integer and for each $\epsilon_i$ we have $0\leq\epsilon_i\leq2$, therefore: $$f(2m_1)+\cdots+f(2m_M)+f(\epsilon_1)+\cdots+f(\epsilon_M)\\ \geq m_1f(2)+\cdots+m_Mf(2)+(\epsilon_1^2-\epsilon_1)+\cdots+(\epsilon_M^2-\epsilon_M)\\ \geq 2m_1+\cdots+2m_M+(\epsilon_1^2-\epsilon_1)+\cdots+(\epsilon_M^2-\epsilon_M)\\ =(2m_1+\epsilon_1)+\cdots+(2m_M+\epsilon_M)+(\epsilon_1^2-2\epsilon_1)+\cdots+(\epsilon_M^2-2\epsilon_M)\\ \geq n_1+\cdots+n_M+(-1)+\cdots+(-1)\\ =M-M=0\\$$ So we conclude that $f(n_1)+\cdots+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+\cdots+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.