22
$\begingroup$

How can we prove that if $f:\mathbb{N}\rightarrow\mathbb{N}$ is a function so that $f(n+1)>f(f(n))$ for all $n\in\mathbb{N}$ then $f(n)=n$ for all $n\in\mathbb{N}$?

  • 1
    Where did you get this problem?2012-12-02
  • 0
    a book Mathematical Olympiad2012-12-02
  • 1
    Fine. Authors, full title, year published, page number please?2012-12-02
  • 0
    Here is http://www.amazon.com/15-000-problems-Mathematical-Olympiads/dp/1448627346/ref=sr_1_1?s=books&ie=UTF8&qid=1354422850&sr=1-1&keywords=15000+problems+from+mathematical+olympiads2012-12-02
  • 0
    [Beni Bogoşel](http://math.stackexchange.com/users/7327/beni-bogosel) posted a [very similar problem](https://mathproblems123.wordpress.com/2012/02/09/functional-equation-on-positive-integers/) on his blog, and indicated (at the time) that he might be willing to add a solution. Unfortunately there's not any more detailed attribution.2012-12-02
  • 2
    IMO 1977 problem 6. My g/f found it online:)2012-12-02
  • 0
    Tengu. Have a solution?2012-12-02

3 Answers 3

16

Claim 1: If $f(k) = 0$ then $k =0$.

Proof: Suppose not. Then there exists $k$ such that $0 = f(k) > f(f(k-1))$, which is not possible, as $f: \mathbb{N} \mapsto \mathbb{N}$.

Claim 2: $f(0) = 0$.

Proof: Let $S = \{f(k) | k > 0\}$. Let $a$ be the smallest number in $S$. Then there exists $k >0$ such that $a = f(k) > f(f(k-1))$. But this means $f(k-1) = 0$. Thus $k=1$, and $f(0) = 0$.

Claim 3: $f(n) = n$.

Proof: Assume, for all $0 \leq m < n$, that $f(k) = m$ iff $k = m$. Now we proceed as in the proofs of Claims 1 and 2.

If $f(k) = n$, then $f(f(k-1)) < n$, which means $k-1 = f(k-1) = f(f(k-1)) < n$. So $k < n+1$, which means that $k = n$.

Let $S = \{f(k) | k > n\}$. Let $a$ be the smallest number in $S$. Thus there exists $k >n$ such that $a = f(k) > f(f(k-1))$. Therefore $f(k-1) \leq n$. But if $f(k-1) < n$, then $f(k-1) = k-1$, and so $k \leq n$. But $k>n$. Therefore, $f(k-1) = n$, and so $k= n+1$ and $f(n) = n$.

  • 0
    Mike. I do not understand your test sequence. In the penultimate sentence why if $ f (k-1) then $ f (k-1) = k-1 $?2012-12-02
  • 0
    @RoinerSeguraCubero: If $f(k-1) then the induction assumption "for all $0 \leq m < n$, $f(k)=m$ iff $k=m$ " applies. Thus $f(k-1)=k-1$.2012-12-02
  • 0
    Mike, if $f(k-1) and if we apply the induction hypothesis then we have $f(f(k-1))=f(k-1)$ and only if f is injective we can say that $f(k-1)=k-1$. Or am I wrong?2012-12-02
  • 0
    @RoinerSeguraCubero: No, I'm not making any global assumptions about $f$ being injective. The induction hypothesis is that if $f$ maps $k$ to any value $m$ smaller than $n$ then $k$ must be $m$, and so $f$ maps $k$ to itself. I suppose the induction hypothesis could be thought of implying that $f$ is injective in a local sense, but I didn't think of it that way. In other words, $f(k-1) = k-1$ precisely because $f(k-1) < n$. If $f(k-1) \geq n$, then we wouldn't be able to claim that $f(k-1) = k-1$ (at least at this point in the proof.)2012-12-02
  • 0
    Mike. In the last line why if $f(k-1) = n$, and so $k= n+1$?2012-12-02
  • 0
    @RoinerSeguraCubero: We know $f(k-1) \leq n$. Since $f(k-1) < n$ implies $k \leq n$, and we know $k > n$, we must have $f(k-1) = n$. In the previous paragraph we showed that if $f(k) = n$ then $k=n$. Therefore, $f(k-1) = n$ implies $k-1=n$, and so $k=n+1$.2012-12-02
  • 0
    Mike. Why in the previous paragraph $f(k-1)=k-1$?2012-12-02
  • 0
    Mike. In the claim 3, with the second paragraph you show that if $k\geq n$ and $f(k)=n$ then $k=n$. Then why you write the third paragraph?2012-12-02
  • 0
    @RoinerSeguraCubero: In the second paragraph of Claim 3, $f(f(k-1)) < n$ means that we can apply the induction hypothesis. Thus $f(f(k-1)) = f(k-1)$. But then this means that $f(k-1) < n$, so we can apply the induction hypothesis again to get $f(k-1) = k-1$.2012-12-03
  • 0
    @RoinerSeguraCubero: The second paragraph of Claim 3 involves a conditional: IF $f(k) = n$ THEN $k=n$. I don't know at that point that $f$ actually does map $n$ to itself. The point of paragraph 3 of Claim 3 is to prove that $f$ truly does map $n$ to itself. There's a parallel here with Claims 1 and 2. Claim 1 says "if $f(k) = 0$ then $k=0$." I don't know that $f$ actually does map $0$ to itself until I prove it with Claim 2.2012-12-03
  • 1
    Excellent Mike. Thanks :)2012-12-03
  • 0
    @MikeSpivey: In the proof of claim 3 : from $f(f(k-1)) , how does it follow $f(f(k-1))=f(k-1)$ ?2015-01-03
  • 0
    @SouvikDey: Since $f$ maps $f(k-1)$ to some value strictly smaller than $n$, the induction hypothesis applies, and so $f(f(k-1)) = f(k-1)$. (The induction hypothesis is stated in the first paragraph of Claim 3; namely, that if $f$ maps $k$ to some value $0 \leq m < n$, then the input $k$ is equal to the output $m$. The claim $f(f(k-1)) = f(k-1)$ is just saying that the input $f(k-1)$ is equal to the output $f(f(k-1))$.)2015-01-05
1

Attempted solution (Improvements/corrections are greatly welcome!):

Clearly, the function isn't constant on any interval. So it must be either strictly increasing or strictly decreasing.

Suppose the function isn't injective. Then there exist $a,b \in \mathbb{N}$ such that $f(a) = f(b)$, but $a \neq b$. So either $a>b$ or $a. WLOG, let $a>b$. Then $a = b+m$, for some $m \in \mathbb{N}$. Now, $f(a) = f(b+m) > f(f(b+(m-1)) > f(f(f(b+m-2) > ... >f(f(...(f(b))...)$. Now, suppose, WLOG that $f$ is increasing (if $f$ is decreasing, then there is also a contradiction). Then $f(f(...(f(b))...) > f(b)$. But $f(b) = f(a)$. Thus, we have a contradiction. So, $f$ must be injective.

Now, apply $f^{-1}$ on both sides, and you get that $n+1 > f(n)$, $\forall n \in \mathbb{N}$.

Clearly, if $ \forall n \in \mathbb{N}$, $f(n) = a*n+b$, where $a \neq 1$ and $b \neq 0$, then it would contradict $n+1 > f(n)$, $\forall n \in \mathbb{N}$.

Now it's just left to see what happens if there exists an $n'$ where $f(n') \neq n'$. In such a case, $f(n')>n'$ or $f(n'). Check that both cases still lead to contradictions.

I think if you can somehow rule out that $f$ is decreasing, then this might work.

  • 1
    Hello, thanks for the advice. I think I've completed my answer for this question, and will be sure to follow your advice in the future.2012-12-02
  • 0
    Cubby why $f$ is increase?2012-12-02
  • 0
    You are right, it doesn't have to be increasing. Let me improve my solution.2012-12-02
  • 0
    Ah, now I remember why it has to be strictly increasing. Because if it is strictly decreasing, then $f(0) < 0$, which implies that $f(0) \notin \mathbb{N}$.2012-12-02
  • 0
    Why can't it be a constant in any interval?2012-12-02
  • 0
    Remember why? You have seen this before?2012-12-02
  • 5
    Not constant on any interval is not the same as strictly increasing or decreasing. The sequence that alternates 0,1 is not constant nor strictly increasing or decreasing.2012-12-02
0

Another proof :

  1. We first show the property Pn is true for all n : Pn : (Forall k >= n, f(k)>=n) [">=" means "greater than or equal to"]

    Proof by Induction : 1/ P0 is true, since forall k, f(k) >= 0 2/ forall n, if Pn is true, then forall k >=n+1 ; k-1 >= n then f(k-1)>= n then f(f(k-1)) >=n and f(k) > f(f(k-1)) >=n thus f(k) >= n+1 then P(n+1) is true

  2. Forall n, since Pn is true, take k=n, then f(n)>=n

  3. Then forall n, f(f(n)) >= f(n) then the starting hypothesis yields:
    f(n+1)>f(n) then f is strictly growing. Thus the starting hypothesis implies : forall n, n+1> f(n)

  4. Thus for all n : n+1>f(n)>=n this f(n) = n...

  • 0
    Please, use [MathJax](https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference) to format mathematical expressions.2018-01-16