Find all functions $f:\mathbb{N}\rightarrow\mathbb{N}$ such that \[f(n+1)>\frac{f(n)+f(f(n))}{2}\] for all $n\in\mathbb{N}$, where $\mathbb{N}$ is the set of strictly positive integers.
Problem
Source: Saudi Arabia IMO TST Day I Problem 4
Tags: function, induction, algebra unsolved, algebra
23.07.2014 12:56
First, we have $ f(n) \ge 1 \forall n \in \mathbb{N} $ since $ f $ is define on $ \mathbb{N} $. Now, we use induction to prove: $ f(n) \ge n $. Suppose $ f(n) \ge a \forall n \ge a $. Then by the assumption we get: $ f(n+1) > \frac{f(n)+f(f(n))}{2} \ge \frac{a+a}{2} =a \rightarrow f(n+1) \ge a+1 $. Thus, $ f(n) \ge n $ !! [$ f(n+1)-f(n) > f(f(n))-f(n+1) \ge f(n)-f(n+1) \rightarrow f(n+1)>f(n) $ And if there is a nature number $ b $ such that $ f(b)>b+1 $, we could do the same trick to get that $ f(n) > n+1 \forall n \ge b $. So, $ f(n+1)-f(n) > f(f(n))-f(n+1) \ge f(n+2)-f(n+1) \forall n \ge m $ (which contradicts to $ f(n) \ge n $.) Finally, suppose $ f(c)=c+1 $ then : $ c+2 \ge f(c+1) > f(c)+f(f(c))-f(c+1)=c+1 \rightarrow f(c+1)=c+2 $. $ \Rightarrow f(n)=n \forall n<m ,f(n)=n+1 \forall n \ge m $!
23.07.2014 15:16
Another solution: It is trivial to prove that $f(n) \ge n$.Note that $f(n)=n$ is a solution.Suposse that that isn't the case.Now look at the numbers: $ f(1)-1,f(2)-2, \cdots ,f(n)-n $ and let $ k $ be the biggest number of these.Now let $b$ be the smallest number such that $f(b)-b=k$.Now let $a$ be the first number greater than $b$ such that $f(a+1)-(a+1)<k$.We have $a+1+(k-1)\ge f(a+1)>\frac{f(a)+f(f(a))}{2}=\frac{a+k+f(a+k)}{2}\ge a+k$ which is a contradiction so after some number $b$ every number will satisfy $f(n)=n+k$.Now consider some $n>b$.We have $ f(n+1)>\frac{f(n)+f(f(n))}{2} $ which is equivalent to $n+k+1>\frac{2n+3k}{2}$ which implies $k<2$ so $k=1$.So the function will be: $f(n)=n,n<b$ and $ f(n)=n+1,n\ge b$.