- #1
- 19,445
- 10,025
Written by micromass:
I have recently posted a challenge in my signature. The challenge read as follows:
The first answer I got was from Millenial. He gave the following correct solution:
This solution is very elegant. But there are other solutions. For example, we can prove the following chain of implications:
The proof is as follows:
Yet another proof consists of proving that ##f## is a concave function. This means that for each ##x## and ##y## and ##t\in [0,1]## that
[tex]f(tx + (1-t)y) \geq tf(x) + (1-t)f(y)[/tex]
Visually, it means that
So, the straight line between two points is always below the actual function.
Here is the proof that any function such that ##f^{\prime\prime}<0## is concave:
Now, we can immediately prove again that ##tf(x)\leq f(tx)## for each ##x## and ##t\in [0,1]##. Indeed, apply concavity with ##y=0## (and remember that ##f(0) = 0##, then
[tex]tf(x) = tf(x) + (1-t)f(0) \leq f(tx + (1-t)y)\leq f(tx)[/tex]
We can then, as before, prove ##f(x+y)\leq f(x) + f(y)##.
Many congratulations to Millenial for solving the problem!
I have recently posted a challenge in my signature. The challenge read as follows:
Let ##f:[0,+\infty )\rightarrow [0,+\infty )## be a twice differentiable function such that ##f(0) = 0##. Prove that if ##f^{\prime\prime}(x)\leq 0## for all ##x##, then ##f(x+y)\leq f(x) + f(y)## for all ##x## and ##y##.
The first answer I got was from Millenial. He gave the following correct solution:
Let [itex]g(x) = f'(x)[/itex]. Then, the question tells us that g(x) is decreasing. We are only interested in cases where x and y are greater than or equal to 0, because that's where f is defined. Define
[tex]\int^{x}_{y} g(t)\,dt = A(x,y)[/tex]
Then, [itex]A(x,0) = f(x)[/itex] where equality follows because [itex]f(0) = 0[/itex].
The question asks us to prove [itex]A(x,0) + A(y,0) \geq A(x+y,0)[/itex]. Without loss of generality, we assume [itex]x\geq y[/itex]. Then, the inequality is reduced to [itex]2A(y,0) + A(x,y) \geq A(y,0) + A(x,y) + A(x+y,x)[/itex], which can be simplified to [itex]A(y,0) \geq A(x+y,x)[/itex].
Using the fact that A denotes integrals, we can put lower and upper bounds on A using maxima and minima of g in the given intervals. We find that [itex]A(y,0) \geq y\cdot g(y)[/itex] and [itex]A(x+y, x) \leq y\cdot g(x)[/itex] because [itex]g(x)[/itex] is decreasing. This means that our question is reduced to proving [itex]y\cdot g(y) \geq y\cdot g(x)[/itex]. Since [itex]y\geq 0[/itex] and the case where [itex]y = 0[/itex] is trivial, we may divide by y to get [itex]g(y) \geq g(x)[/itex], and since [itex]x \geq y[/itex], this is equivalent to saying g is decreasing; which we already know.
This solution is very elegant. But there are other solutions. For example, we can prove the following chain of implications:
- ##f^{\prime\prime}(x)\leq 0## for all ##x\in \mathbb{R}##.
- ##f^\prime## is decreasing.
- ##\frac{f(x)}{x}## is decreasing.
- For each ##t\in [0,1]## and for all ##x## holds that ##tf(x)\leq f(tx)##.
- For each ##x## and ##y## holds that ##f(x+y)\leq f(x) + f(y)##.
The proof is as follows:
From ##(1)## to ##(2)## is just elementary calculus.
From ##(2)## to ##(3)## is as follows. We need to prove that the derivative of ##\frac{f(x)}{x}## is negative. By taking derivatives, we need to prove that ##f^\prime(x) x\leq f(x)## for each ##x##. Apply the mean value theorem on the interval ##[0,x]##. So we know that there is a constant ##c\in [0,x]## such hat
[tex]f(x)= f^{\prime}(c) x[/tex]
Using that ##f^\prime## is decreasing, the inequality follows.
From ##(3)## to ##(4)## follows since ##tx\leq x## and thus ##\frac{f(x)}{x}\leq \frac{f(tx)}{tx}##. Hence the inequality follows.
From ##(4)## to ##(5)## follows from
[tex]\begin{eqnarray*}
f(x) + f(y)
& = & f\left(\frac{x}{x+y}(x+y)\right) + f\left(\frac{y}{x+y} (x+y)\right)\\
& \leq & \frac{x}{x+y}f(x+y) + \frac{y}{x+y} f(x+y) \\
& = & f(x+y)
\end{eqnarray*}[/tex]
Yet another proof consists of proving that ##f## is a concave function. This means that for each ##x## and ##y## and ##t\in [0,1]## that
[tex]f(tx + (1-t)y) \geq tf(x) + (1-t)f(y)[/tex]
Visually, it means that
So, the straight line between two points is always below the actual function.
Here is the proof that any function such that ##f^{\prime\prime}<0## is concave:
Assume that ##f^{\prime\prime}\leq 0##. Take ##x<y## and ##t\in (0,1)##. Let ##z = tx + (1-t)y## and thus ##x< z < y##. By the mean value theorem, there are ##u## and ##v## such that ##x<u<z<v<y## and such that ##f(z) - f(x) = f^\prime(u) (z-x)## and ##f(y) - f(z) = f^\prime(v) (y-z)##. Since ##f^\prime## is decreasing, we have ##f^\prime(v)\leq f^\prime(u)##. Hence
[tex]\frac{f(y) - f(z)}{y-z}\leq \frac{f(z) - f(x)}{z-x}[/tex]
Since ##z = tx + (1-t)y##, we see that
[tex]\frac{f(y) - f(z)}{t(y-x)} \leq \frac{f(z) - f(x)}{(1-t)(y-x)}[/tex]
And thus
[tex](1-t)( f(y) - f(z) ) \leq t(f(z) - f(x))[/tex]
The desired inequality follows.
Now, we can immediately prove again that ##tf(x)\leq f(tx)## for each ##x## and ##t\in [0,1]##. Indeed, apply concavity with ##y=0## (and remember that ##f(0) = 0##, then
[tex]tf(x) = tf(x) + (1-t)f(0) \leq f(tx + (1-t)y)\leq f(tx)[/tex]
We can then, as before, prove ##f(x+y)\leq f(x) + f(y)##.
Many congratulations to Millenial for solving the problem!
Last edited: