5

Let $f$ be a function from $\mathbb{N}$ to $ \mathbb{N}$ such that $\forall n \in \mathbb{N}$, $f(f(n)) <f(n+1)$.

Prove that $\forall k \geq n$, $f(k) \geq n$.

I've put much time and effort to solve this but unfortunately couldn't.

I tried to prove a simpler version $\forall n\geq 0$, $f(n) \geq n$.

for $n = 0$, $f(0) \geq 0$ because it's absurd otherwise.

We can use the same idea to prove that $f(1) \geq 1$ and so on, but as each time you have to find $n$ contredictions. I tried to use recursion, but, you know, I failed.

Can I get some help/hints ? Thanks :D

Stella Biderman
  • 31,155
Noctisdark
  • 383

1 Answers1

3

I think that the simpler version is actually harder to prove than the original question. We can prove the original statement with induction to $n$:

Base case: For $n = 0$ it clearly holds, because $f(k) \geq 0$ for all $k \in \mathbb{N}$.

Inductive step: Suppose that it holds for all $n = m$ with $m \in \mathbb{N}$. Let now $l \geq m+1$, so $l-1 \geq m$. Because the statement holds for $m$, we have $f(l-1) \geq m$. Now we can apply the inductive hypothesis also for $k = f(l-1)$, and we get $f(f(l-1)) \geq m$. Now it follows $f(l) > f(f(l-1)) \geq m$. This is exactly the statement we wanted to prove for $n = m+1$.

Reinier
  • 361