The function $f:\mathbb R^{\ge 0} \longrightarrow \mathbb R^{\ge 0}$ satisfies the following properties for all $a,b\in \mathbb R^{\ge 0}$: a) $f(a)=0 \Leftrightarrow a=0$ b) $f(ab)=f(a)f(b)$ c) $f(a+b)\le 2 \max \{f(a),f(b)\}$. Prove that for all $a,b\in \mathbb R^{\ge 0}$ we have $f(a+b)\le f(a)+f(b)$. Proposed by Masoud Shafaei
Problem
Source: Iran TST 2012-First exam-2nd day-P5
Tags: function, induction, ceiling function, binomial coefficients, algebra proposed, algebra
goodar2006
24.04.2012 15:53
It's obvious that $f(1)=1$, $f(a^2)=(f(a))^2$, $f(2a)\le2f(a)$ and $f(\frac{1}{a})=\frac{1}{f(a)}$.
Lemma: For every natural number $n$, $f(n)\le 2n$.
Proof:By an easy induction, one can see that for every natural number $m$, $f(2^m)\le 2^m$, since $f(1)=1$. Now let $n=2^r+s$ where $2^r$ is the greatest power of $2$ less than or equal to $n$. We have $f(n)\le 2\max\{f(2^r),f(a)\}\le \max\{2^{r+1},4a\}\le 2n$.
Is it useful to continue?
goldeneagle
24.04.2012 19:08
goodar2006 wrote:
It's obvious that $f(1)=1$, $f(a^2)=(f(a))^2$, $f(2a)\le2f(a)$ and $f(\frac{1}{a})=\frac{1}{f(a)}$.
Lemma: For every natural number $n$, $f(n)\le 2n$.
Proof:By an easy induction, one can see that for every natural number $m$, $f(2^m)\le 2^m$, since $f(1)=1$. Now let $n=2^r+s$ where $2^r$ is the greatest power of $2$ less than or equal to $n$. We have $f(n)\le 2\max\{f(2^r),f(a)\}\le \max\{2^{r+1},4a\}\le 2n$.
Is it useful to continue?
yes . It is useful..... I have seen official solution ..... But i like to see a solution here (Maybe by PCO) , so i will post it later....not now! No one could solve it during exam....
jjax
25.04.2012 18:32
I'm in a hurry, so here's a brief outline of my solution. Note first that $2(f(a)+f(b)) \geq 2max(f(a),f(b)) \geq f(a+b)$. Also note that $2n \geq f(n)$ for naturals $n$, as posted by goodar2006. Proceed by contradiction. Assume that $f(a+b)=k(f(a)+f(b))$ for some $k>1$ and $a,b$. Now, for some large $n$, we have $\frac{k^n}{2^{ \lceil log_2 (n+1) \rceil +1} } >1$. $f(a+b)^n = k^n (f(a)+f(b)^n) = k^n (f(a)^n +nf(a)^{n-1}f(b)+...) $ $\geq \frac{ k^n}{2} (f(a^n)+f(n)f(a)^{n-1}f(b)+...)$ since binomial coefficients are integers. $=\frac{ k^n}{2} (f(a^n)+f(na^{n-1}b)+...)$ where there are $n+1$ $f$s. Each step, we halve the number of $f$s and merge them together: $\geq \frac{ k^n}{4} (f(a^n+na^{n-1}b)+...)$ ... $\geq \frac{k^n}{2^{ \lceil log_2 (n+1) \rceil +1} }f(a^n+...)=\frac{k^n}{2^{ \lceil log_2 (n+1) \rceil +1} } f(a+b)^n>f(a+b)^n$. Contradiction.
goldeneagle
01.05.2012 21:21
very similar to this one : Poland 2010 One of my friends found this problem yesterday!!!
Swistak
01.06.2012 16:50
I'm from Poland and I was solving problem posted above during national final two years ago but I didn't solve it. And during solving this problem from Iran TST I thought about similarity of them, but although I know 2 solutions to polish problem, it appears that they don't work in this problem, so in my opinion only thing which these problems have is only similar matter. I didn't solve Iran's problem also, but I had idea, which possibly can be used in this. Maybe anybody is able to end this solution? Let $h: \mathbb {R} \rightarrow \mathbb {R}$ be a functiion such that $e^{h(ln x)}=f(x)$. Then $h(x+y)=h(x)+h(y)$. If $h(x)=cx$ we obtain $f(x)=a^c$ for $c \leq 1$, so our thesis follows, but I don't know what to do if $h$ isn't linear and is one of those freaky Cauchy's function. Then $f$ is dense in $\{ (x, y) \in \mathbb{R} : x,y>0 \} $, but so what?
Ankoganit
29.03.2017 13:47
Let's begin with some preliminary observations. First off, setting $b=1$ is (b) gives $f(1)=1$, and setting $a=b=1$ in (c) gives $f(2)\le 2f(1)=2$. Obviously, multiplicativity nicely generalizes to any number of variables; for example, $f(abc)=f(ab)f(c)=f(a)f(b)f(c)$. Also, setting $a=b=x$ in (b) gives $f(x^2)=f(x)^2$. This is going to be useful. Now define a sequence $\langle c_i\rangle _{i=0}^{\infty}$ as follows: $$c_i=\begin{cases} 2 & \text{ if }i=0,\\ \displaystyle\sqrt{\frac{2c_{i-1}^2+c_{i-1}}{3}} & \text{ if }i\ge 1.\end{cases}$$We claim that $f(a+b)\le c_i \left(f(x)+f(y)\right)$ for all $i\in \mathbb N_0$ and all $a,b\in\mathbb R^{\ge 0}$. Let's do induction on $i$. For $i=0$ we need to prove $f(a+b)\le 2\left(f(a)+f(b)\right)$; but c'mon, that's obvious: $f(a+b)\le 2\max\{f(a),f(b)\}\le 2\left(f(a)+f(b)\right).$ Now time to make the jump from $i$ to $i+1$. We have \begin{align*} f(x+y)^2 &= f((x+y)^2)\\ &=f(x^2+2xy+y^2)\\ &\le c_if(x^2)+c_if(2xy+y^2)\\ & \le c_if(x^2)+c_i^2f(2xy)+c_i^2f(y^2) && (1)\end{align*}In a similar fashion, we would get \begin{align*} f(x+y)^2 & \le c_i^2f(x^2)+c_if(2xy)+c_i^2f(y^2) && (2)\\ f(x+y)^2 &\le c_i^2f(x^2)+c_i^2f(2xy)+c_if(y^2) && (3)\end{align*}Adding these up, \begin{align*} 3f(x+y)^2& \le (2c_i^2+c_i)\left(f(x^2)+f(2xy)+f(y^2)\right)\\ &= (2c_i^2+c_i)\left(f(x)^2+f(2)f(x)f(y)+f(y)^2\right)\\ &\le (2c_i^2+c_i)\left(f(x)^2+2f(x)f(y)+f(y)^2\right)\\ &\le (2c_i^2+c_i)(f(x)+f(y))^2\\ \implies f(x+y)& \le \sqrt{\frac{2c_i^2+c_i}{3}}\left(f(x)+f(y)\right)\\ &\le c_{i+1}(f(x)+f(y)).\end{align*}This completes the induction. Now focus on the sequence $\langle c_i\rangle _{i=0}^\infty$. It is rather easy to establish by induction that $1\le c_i$ for all $i$ and that it's a monotone decreasing sequence. So by monotone convergence theorem, this sequence converges; let's say the limit is $c$. Then taking $i\to \infty$ in the relation $c_{i+1}=\sqrt{\frac{2c_i^2+c_i}{3}}$ gives $c=\sqrt{\frac{2c^2+c}{3}}\implies c\in\{0,1\}$. The case $c=0$ can be eliminated because of $x_i\ge 1$ as we saw before; so $\lim_{i\to\infty} c_i=1$. Now invoking $f(a+b)\le c_i \left(f(x)+f(y)\right)$ immediately gives $f(a+b)\le f(a)+f(b)$, as desired. $\blacksquare$