9
$\begingroup$

Function $f:[0,1]\rightarrow \Bbb R$ holds in the following conditions :
1) $f(1)=1$
2) $\forall x \in [0,1]: f(x)\geq 0$
3) $\forall x,y,x+y \in [0,1]: f(x+y)\geq f(x)+f(y)$.
Prove that $\forall x \in [0,1] : f(x)\leq 2x$

I tested values $0,\frac12$ in the given formula and got the following results:
$$f(0)=0 , f(\frac12)\leq \frac12,f(x)\leq \frac{f(2x)}{2}$$
Please help complete the proof.

$\endgroup$
  • 2
    $\begingroup$ I think a lot of intuition comes from drawing the picture (comparing with the line $y=2x$). You know $f$ is nondecreasing and upper-bounded by 1. You can easily show the result holds for $x \in [1/2, 1]$. Now show it for $[1/4, 1/2]$, then for $[1/8,1/4]$, and so on. $\endgroup$ – Michael Nov 4 '17 at 9:59
  • $\begingroup$ @Michael Maybe you could post your own answer $\endgroup$ – Hamid Reza Ebrahimi Nov 4 '17 at 10:39
7
$\begingroup$

Case 1: $x ≥ 1/2$.

Let $x \in [0,1]$, and set $y = 1 - x$. Then $1 = f(x+y)≥ f(x)+f(y) ≥ f(x)$. This tells us that $f$ is bounded above by $1$. Hence to show that $f(x) ≤ 2x$ for all $x \in [0,1]$, it now suffices to show that it holds for $x < 1/2$. (If $x ≥ 1/2$, then $f(x) ≤ 1 ≤ 2x$ so we are done.)

Case 2: $1/4 ≤ x < 1/2$.

We also have, as you discovered, $$f(1/2) = \frac{f(1/2)+f(1/2)}{2} \leq \frac{f(1)}{2} = \frac{1}{2}$$ Let $x \in [0,1/2)$. Let $y = 1/2-x$. Then $1/2 ≥ f(x+y) ≥ f(x) + f(y) ≥ f(x)$. So now, by the same argument as case 1, we have $f(x) ≤ 2x$ for $x ≥ 1/4$.

Case 3: $1/8 ≤ x < 1/4$. $$f(1/4) = \frac{f(1/4)+f(1/4)}{2} \leq \frac{f(1/2)}{2} ≤ \frac{1}{4}$$

Can you see the pattern? Given any $x \in (0,1]$, a "finite descent" tells us that $f(x) ≤ 2x$. As for $x = 0$, we see that $0≤ f(0) ≤ f(1+0) - f(1) = 1-1 = 0$.

Hence we are done!

$\endgroup$
  • $\begingroup$ How come you get 6 votes and I only get 1? (Well, now I upvote you to 7). Am going to bed now, have a good night (or morning, or wherever you are). $\endgroup$ – Michael Nov 4 '17 at 10:28
  • $\begingroup$ @Harambe Why $1/2 \geq f(x+y)$ ? $\endgroup$ – Hamid Reza Ebrahimi Nov 4 '17 at 10:28
  • $\begingroup$ Because in the line above it, we showed that $f(1/2) ≤ 1/2$, and we chose $y$ so that $x+y = 1/2$ $\endgroup$ – Harambe Nov 4 '17 at 10:30
2
$\begingroup$

By induction, (3) easily generalizes to

$$ \forall x_1,x_2,\ldots x_n, x_1+x_2+\ldots+x_n\in [0,1], f\bigg(\sum_{k=1}^n x_k \bigg) \geq \sum_{k=1}^n f(x_k) \tag{4} $$

Putting $x_1=x_2=\ldots=x_n=\frac{1}{n}$ in (4) and using (1), we deduce :

$$ f(\frac{1}{n}) \leq \frac{1}{n} \tag{5} $$

Now, let $x\in [0,1]$ with $x\neq 0$. There is an integer $k$ such that $\frac{1}{2^{k+1}} \lt x \leq \frac{1}{2^k}$. Using (3) with $y=\frac{1}{2^k}-x$, we deduce $f(x)\leq f(\frac{1}{2^k})$. But $f(\frac{1}{2^k}) \leq \frac{1}{2^k}$ by (5), and hence $f(x) \leq \frac{1}{2^k} \leq 2x$ as wished.

All that's left is the case $x=0$. But this is easy : taking $x_1=x_2=\ldots=x_n=0$ in (4) and using (1), we have $f(0) \leq \frac{1}{n}$ for all $n$, whence $f(0)\leq 0$ by pasing to the limit, whence $f(0)=0$ by (2).

$\endgroup$
2
$\begingroup$

$f(0)=0$ so $f(0)\le2\times0$

$f(1)=1$ so $f(1)\le2\times1$

Take $x=y=\frac{1}{2}$, we get

$f(\frac{1}{2}) \le \frac{1}{2}f(1) = \frac{1}{2}$

Take $x=y=1/4$, we get

$f(\frac{1}{4}) \le \frac{1}{2}f(\frac{1}{2}) = \frac{1}{4}$

So, $f(\frac{1}{2^n}) \le \frac{1}{2^n}$

Also, $f$ is nondecreasing and it's range is $[0,1]$.

Thus, for $[0,1]$, $f(x)\le 2x$

$\endgroup$
  • $\begingroup$ Every nondecreasing $f:[0,1]\to[0,1]$ satisfies $f(x)\leq 2x$? $\endgroup$ – Bart Michels Nov 4 '17 at 10:08
  • 1
    $\begingroup$ @barto That, along with the evidence $f(\frac{1}{2^n}) \le \frac{1}{2^n}$, it must satisfy the condition. $\endgroup$ – Maadhav Gupta Nov 4 '17 at 10:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.