We are given a positive, non-decreasing function $f$ defined on natural numbers with $f(0) = 0$. $f$ has a submodularity-like property:

$f(x+y) \leq f(x) + f(y) $

for all natural numbers $x$ and $y$.

Can we then show that for any natural numbers $x,y$, we have

$f(x) \geq \frac{x}{x+y}f(x+y)$?

  • $\begingroup$ Well, I figured out that for fixed two number x,y the at least one of the inequalities must happens, i.e., for x or for y. $\endgroup$ – checkmath Feb 20 '12 at 2:17
  • $\begingroup$ Functions and sequences with the above property are usually called subadditive. There is a chapter in the book An introduction to the theory of functional equations and inequalities by Marek Kuczma devoted to subadditive function on $\mathbb R$. I do not know off-hand about a reference that would contain a detailed study of subadditive sequences. $\endgroup$ – Martin Sleziak Mar 18 '12 at 6:58


For example pick $f(1) = f(2) = 1$ and $f(n)=2$ for $n \ge 2$. Then $1 = f(2) < \frac 23 f(3) = \frac 43$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.