Demostrar que $f(n) \geq n$

Question

Deje $f$ ser una función de $\mathbb{N}$ $ \mathbb{N}$tal que $\forall n \in \mathbb{N}$, $f(f(n)) <f(n+1)$.

Demostrar que $\forall k \geq n$, $f(k) \geq n$.

He puesto mucho tiempo y esfuerzo para resolver esto, pero por desgracia no pudimos.

Traté de probar una versión más simple $\forall n\geq 0$, $f(n) \geq n$.

para $n = 0$, $f(0) \geq 0$ porque es absurdo lo contrario.

Podemos utilizar la misma idea para demostrar que $f(1) \geq 1$ y así sucesivamente, pero como cada vez que usted tiene que encontrar la $n$ contredictions. He intentado utilizar la recursividad, pero, usted sabe, yo no.

Puedo obtener alguna ayuda/sugerencias ? Gracias :D

Answer 1

Creo que la versión más simple es en realidad más difícil de probar que la pregunta original. Podemos probar la declaración original con la inducción a $n$:

Caso Base: Para $n = 0$ se sostiene claramente, porque $f(k) \geq 0$ todos los $k \in \mathbb{N}$.

Inductivo paso: Supongamos que se tiene para todos los $n = m$$m \in \mathbb{N}$. Vamos ahora a $l \geq m+1$, lo $l-1 \geq m$. Debido a que la instrucción tiene por $m$,$f(l-1) \geq m$. Ahora podemos aplicar la hipótesis inductiva también para $k = f(l-1)$, y llegamos $f(f(l-1)) \geq m$. Ahora sigue a $f(l) > f(f(l-1)) \geq m$. Esta es exactamente la declaración que quería probar para $n = m+1$.