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}$?


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$.

  • $\begingroup$ Mike. I do not understand your test sequence. In the penultimate sentence why if $ f (k-1) <n $ then $ f (k-1) = k-1 $? $\endgroup$ – Roiner Segura Cubero Dec 2 '12 at 18:35
  • $\begingroup$ @RoinerSeguraCubero: If $f(k-1)<n$ then the induction assumption "for all $0 \leq m < n$, $f(k)=m$ iff $k=m$ " applies. Thus $f(k-1)=k-1$. $\endgroup$ – Mike Spivey Dec 2 '12 at 21:03
  • $\begingroup$ Mike, if $f(k-1)<n$ 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? $\endgroup$ – Roiner Segura Cubero Dec 2 '12 at 21:44
  • $\begingroup$ @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.) $\endgroup$ – Mike Spivey Dec 2 '12 at 21:47
  • 1
    $\begingroup$ Excellent Mike. Thanks :) $\endgroup$ – Roiner Segura Cubero Dec 3 '12 at 0:49

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<b$. 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')<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
    $\begingroup$ 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. $\endgroup$ – chubbycantorset Dec 2 '12 at 3:18
  • $\begingroup$ Cubby why $f$ is increase? $\endgroup$ – Roiner Segura Cubero Dec 2 '12 at 3:29
  • $\begingroup$ You are right, it doesn't have to be increasing. Let me improve my solution. $\endgroup$ – chubbycantorset Dec 2 '12 at 3:38
  • $\begingroup$ 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}$. $\endgroup$ – chubbycantorset Dec 2 '12 at 3:46
  • 5
    $\begingroup$ 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. $\endgroup$ – Ross Millikan Dec 2 '12 at 4:15

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...

  • $\begingroup$ Please, use MathJax to format mathematical expressions. $\endgroup$ – mucciolo Jan 16 '18 at 17:46

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.