Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Where did you get this problem? –  Will Jagy Dec 2 '12 at 4:16
    
a book Mathematical Olympiad –  Roiner Segura Cubero Dec 2 '12 at 4:29
    
Fine. Authors, full title, year published, page number please? –  Will Jagy Dec 2 '12 at 4:32
    
2  
IMO 1977 problem 6. My g/f found it online:) –  Tengu Dec 2 '12 at 15:05
show 2 more comments

2 Answers

up vote 9 down vote accepted

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

share|improve this answer
    
Mike. I do not understand your test sequence. In the penultimate sentence why if $ f (k-1) <n $ then $ f (k-1) = k-1 $? –  Roiner Segura Cubero Dec 2 '12 at 18:35
    
@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$. –  Mike Spivey Dec 2 '12 at 21:03
    
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? –  Roiner Segura Cubero Dec 2 '12 at 21:44
    
@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.) –  Mike Spivey Dec 2 '12 at 21:47
1  
Excellent Mike. Thanks :) –  Roiner Segura Cubero Dec 3 '12 at 0:49
show 6 more comments

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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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