Concave functions on discrete domain

672 Views Asked by At

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

1

There are 1 best solutions below

0
On

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$