1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Feb 12, 2015 #1
    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 [itex]f: [0, \infty) \rightarrow [0, \infty)[/itex] where [itex]f(0) = 0, f(x) > 0, x \neq 0 [/itex] 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 [itex] f(a) > f(b)[/itex] for some [itex]a < b[/itex]. That gives me [itex]f(a) - f(b) > 0[/itex], but I don't see how to proceed. I know that [itex]f(a + b) \leq f(a) + f(b)[/itex], i.e. the function is subadditive, but once again, I'm stuck.
     
  2. jcsd
  3. Feb 12, 2015 #2

    DEvens

    User Avatar
    Education Advisor
    Gold Member

    Are you in fact required to use proof by contradiction?

    Can you show something about the derivative based on the inequalities you have?
     
  4. Feb 12, 2015 #3

    RUber

    User Avatar
    Homework Helper

    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.
     
  5. Feb 12, 2015 #4
    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 [itex]f(0t + (1-t)b) \geq tf(0)+(1-t)f(b) = (1-t)f(b)[/itex], but I don't see where that gets me. Since f(a) must lie above that line, I have that [itex]f(a) > f(b)[/itex], but that's already given in the assumption that I'm trying to contradict.
     
  6. Feb 12, 2015 #5
    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.
     
  7. Feb 12, 2015 #6

    DEvens

    User Avatar
    Education Advisor
    Gold Member

    That would be concave downwards. But clearly such a function cannot be always increasing. Your description seems to indicate concave upwards.
     
  8. Feb 12, 2015 #7
    The book just says this function is concave, i.e. [itex]f(tx + (1-t)y) \geq tf(x) + (1-t)f(y)[/itex] when [itex]t \in [0, 1], \forall x, y \in [0, \infty)[/itex]. 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.
     
  9. Feb 12, 2015 #8

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  10. Feb 12, 2015 #9

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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
    [tex] \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} [/tex]
    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##?
     
  11. Feb 12, 2015 #10

    RUber

    User Avatar
    Homework Helper

    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 ##.
     
  12. Feb 12, 2015 #11

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: How do I use proof by contradiction to show that a concave function is always increasing?
Loading...