# How do I use proof by contradiction to show that a concave function is always increasing?

1. Feb 12, 2015

### statsmichael

1. The problem statement, all variables and given/known data
My question is similar to this one (https://www.physicsforums.com/threads/metric-function-composed-with-concave-function.566338/), I think. I have a concave function $f: [0, \infty) \rightarrow [0, \infty)$ where $f(0) = 0, f(x) > 0, x \neq 0$ and I need to show that this function is always increasing, or at least non-decreasing.

2. Relevant equations

3. The attempt at a solution
I'm trying a proof by contradiction. If the function isn't increasing, then $f(a) > f(b)$ for some $a < b$. That gives me $f(a) - f(b) > 0$, but I don't see how to proceed. I know that $f(a + b) \leq f(a) + f(b)$, i.e. the function is subadditive, but once again, I'm stuck.

2. Feb 12, 2015

### DEvens

Are you in fact required to use proof by contradiction?

Can you show something about the derivative based on the inequalities you have?

3. Feb 12, 2015

### RUber

By definition of a concave function, the line connecting any two points (x, f(x)) and (y,f(y)) will lie above the graph of the function.
You have a<b and f(a)>f(b).
Since your function is only looking at [0,infty] there must be a minimum value on [0,a], given that f(0)=0, that is a good start.
Connecting (0,0) to (b,f(b)) should contradict the definition of concavity.

4. Feb 12, 2015

### statsmichael

I thought the definition of a concave function was that any line connecting two points (x, f(x)) and (y, f(y)) will lie BELOW the graph. Isn't that the correct interpretation of the definition (see Wikipedia, for example: https://en.wikipedia.org/wiki/Concave_function)

If I look at the line between (0, f(0)) = (0, 0) and (b, f(b)), I can get that $f(0t + (1-t)b) \geq tf(0)+(1-t)f(b) = (1-t)f(b)$, but I don't see where that gets me. Since f(a) must lie above that line, I have that $f(a) > f(b)$, but that's already given in the assumption that I'm trying to contradict.

5. Feb 12, 2015

### statsmichael

This is in an analysis textbook that I'm working through, and it mentions that since we haven't encountered differentiation in the course yet (it's in the section on basic metric spaces), I should be able to prove it without using anything besides proof by contradiction.

6. Feb 12, 2015

### DEvens

That would be concave downwards. But clearly such a function cannot be always increasing. Your description seems to indicate concave upwards.

7. Feb 12, 2015

### statsmichael

The book just says this function is concave, i.e. $f(tx + (1-t)y) \geq tf(x) + (1-t)f(y)$ when $t \in [0, 1], \forall x, y \in [0, \infty)$. That's concave downwards, right? Concave upwards is the same as convex, right?

If the function can't be increasing, it can at least be non-decreasing, I think.

8. Feb 12, 2015

### Ray Vickson

In many modern textbooks, papers, monographs, etc. (especially in the area of optimization theory and practice) the terminologies "concave up" and "concave down" have been abandoned. They have been replaced by "convex" and "concave". Typical convex functions would be $x^2$, $e^x$ or $e^{-x}$, while typical concave functions would be $-x^2$, $-e^x$ or $-e^{-x}$. More generally, $f$ concave implies that the interpolating line-segment from $(x_1,f(x_1))$ to $(x_2,f(x_2))$ lies on or below the graph $y = f(x)$ between $x_1$ and $x_2$. For a convex function, it lies above instead of below.

9. Feb 12, 2015

### Ray Vickson

Without assuming differentiability, see if you can establish the following (true) statements. If $f$ is concave on a convex subset $I \subset \mathbb{R}$, then for any $x_1 < x_2 < x_3$ in $I$ we have
$$\frac{f(x_2)-f(x_1)}{x_2 - x_1} \geq \frac{f(x_3) - f(x_1)}{x_3 - x_1} \geq \frac{f(x_3) - f(x_2)}{x_3 - x_2}$$
with strict inequalities if $f$ is strictly concave on $I$. (I suggest you draw a picture to see what these are saying.) Basically, these follow by looking at $x_2$ as a appropriate convex combination of $x_1$ and $x_3$.

So, if we have $x_1 < x_2$ but $f(x_1) > f(x_2)$, what would the inequalities above tell you about the behavior of $f(x)$ for $x > x_2$?

10. Feb 12, 2015

### RUber

Okay, so I was flipped upside down in my earlier post. If you have a concave function and it starts decreasing, it will continue decreasing, eventually driving f(x) < 0 for some large x.
In your description of the function, f: [0, infty) --> [0, infty). This is the part that will be contradicted, since an infinitely large x will have to generate a negative f(x) if f is decreasing at any point. Examples of this sort of function are $f(x) = \sqrt{x}; f(x) = \ln x$.

11. Feb 12, 2015

### Ray Vickson

It is your statement "... it starts decreasing, it will continue decreasing..." which needs proof. It is obvious for (piecewise) continuously-differentiable $f$, but needs more work for general concave $f$. An argument as in #9 will go a long way towards a solution.