3
$\begingroup$

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)$?

  • 0
    Functions and sequences with the above property are usually called [subadditive](http://en.wikipedia.org/wiki/Subadditivity). There is a chapter in the book [An introduction to the theory of functional equations and inequalities](http://books.google.com/books?id=rqqvbKOC4c8C) 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.2012-03-18

1 Answers 1

4

No.

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$