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.

  • 0
    Thanks, Henning! I am trying to understand your answer. And I am trying to figure out how to interpret the parametric version. Is it helpful if I add the restrictions that both f and g can only range from 0 to 1?2011-10-06
  • 0
    @Angada, the parametric plot is just there because I'm not sure how to make Wolfram Alpha _not_ display it. It's the ordinary two-function plot that matters.2011-10-06
  • 0
    Hmmm... so I guess it is required to show that $f$ can never equal $g$?2011-10-06
  • 0
    Ok thanks... I thought you were trying to illustrate a point with it that was separate from the regular plot. I'll ignore it.2011-10-06
  • 1
    @Angada: yes, showing $f(x)\ne g(x)$ always would work. But if you can do that, you don't need concavity or monotonicity -- just continuity and a single point where $f(x)>g(x)$.2011-10-06
  • 0
    Is there then any role for concavity in proving inequalities? Or is it entirely irrelevant?2011-10-06
  • 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