1
$\begingroup$

I would like to show that $f(n) > g(n)$ for all $n$ within a certain range.

If I can show that both $f(n)$ and $g(n)$ are strictly increasing with $n$, and that both are strictly concave, and that $f(n) > g(n)$ at both the lower and upper bounds of $n$, is that sufficient?

1 Answers 1

3

No. Consider, for example, $f(x)=1+12x-x^2$ and $g(x)=20x-10x^2$ between $0$ and $1$.

Plotted by Wolfram Alpha.

  • 2
    Since concavity is itself defined by inequalities, at least those inequalities in the definition can be be proved by showing a function is concave. Your problem here is that what you're really dealing with is the _difference_ between the two functions -- and knowing that $f$ and $g$ are both concave does not allow you to conclude anything about their difference. The difference is the sum of the concave $f$ and convex $-g$, and the sum of concave and convex can be anything.2011-10-06