Demostrando que $f(n)=n$ si $f(n+1)>f(f(n))$

Question

¿Cómo podemos demostrar que si $f:\mathbb{N}\rightarrow\mathbb{N}$ es una función tal que $f(n+1)>f(f(n))$ para todos $n\in\mathbb{N}$ entonces $f(n)=n$ para todos $n\in\mathbb{N}$ ?

Este es el problema 6 de la OMI 1977. Lo encontré en este libro .

Answer 1

Reclamación 1 : Si $f(k) = 0$ entonces $k =0$ .

Prueba : Supongamos que no. Entonces existe $k$ tal que $0 = f(k) > f(f(k-1))$ lo que no es posible, ya que $f: \mathbb{N} \mapsto \mathbb{N}$ .

Reclamación 2 : $f(0) = 0$ .

Prueba : Sea $S = \{f(k) | k > 0\}$ . Sea $a$ sea el menor número en $S$ . Entonces existe $k >0$ tal que $a = f(k) > f(f(k-1))$ . Pero esto significa $f(k-1) = 0$ . Así $k=1$ y $f(0) = 0$ .

Reclamación 3: $f(n) = n$ .

Prueba : Supongamos, para todo $0 \leq m < n$ que $f(k) = m$ si $k = m$ . Ahora procedemos como en las pruebas de las afirmaciones 1 y 2.

Si $f(k) = n$ entonces $f(f(k-1)) < n$ lo que significa $k-1 = f(k-1) = f(f(k-1)) < n$ . Así que $k < n+1$ lo que significa que $k = n$ .

Sea $S = \{f(k) | k > n\}$ . Sea $a$ sea el menor número en $S$ . Por lo tanto, existe $k >n$ tal que $a = f(k) > f(f(k-1))$ . Por lo tanto $f(k-1) \leq n$ . Pero si $f(k-1) < n$ entonces $f(k-1) = k-1$ y así $k \leq n$ . Pero $k>n$ . Por lo tanto, $f(k-1) = n$ y así $k= n+1$ y $f(n) = n$ .

Answer 2

Otra prueba :

1. Primero mostramos la propiedad $P_n$ es cierto para todos $n$ $\\$ $P_n : (\forall k \geq n \implies f(k) \geq n)$

   Demostración por inducción : (i) $P_0$ es verdadera, ya que $\forall k \geq 0 ( f(k) \geq 0)$ (ii) $\forall n$ si $P_n$ es cierto, entonces $\forall k \geq n+1 ; k-1 \geq n$ entonces $f(k-1) \geq n$ entonces $f(f(k-1)) \geq n$ y $f(k) > f(f(k-1)) \geq n$ así $f(k) \geq n+1$ Por lo tanto $P_{n+1}$ es cierto.

2. $\forall n$ ya que $P_n$ es cierto, toma $k=n$ entonces $f(n) \geq n$

3. Entonces $\forall n, f(f(n)) \geq f(n)$ entonces se cumple la hipótesis de partida:
   $\\$ $f(n+1)>f(n)$ entonces $f$ está creciendo estrictamente. Por tanto, la hipótesis de partida implica : $\forall n, n+1> f(n)$

4. Así, para todos $n$ , $n+1>f(n)>=n$ . Por lo tanto, $f(n) = n$

Answer 3

Solución intentada (¡las mejoras/correcciones son bienvenidas!):

Es evidente que la función no es constante en ningún intervalo. Así que debe ser estrictamente creciente o estrictamente decreciente.

Supongamos que la función no es inyectiva. Entonces existe $a,b \in \mathbb{N}$ tal que $f(a) = f(b)$ pero $a \neq b$ . Así que $a>b$ ou $a<b$ . WLOG, que $a>b$ . Entonces $a = b+m$ para algunos $m \in \mathbb{N}$ . Ahora, $f(a) = f(b+m) > f(f(b+(m-1)) > f(f(f(b+m-2) > ... >f(f(...(f(b))...)$ . Ahora, supongamos, WLOG que $f$ es creciente (si $f$ es decreciente, entonces también existe una contradicción). Entonces $f(f(...(f(b))...) > f(b)$ . Pero $f(b) = f(a)$ . Por lo tanto, tenemos una contradicción. Entonces, $f$ debe ser inyectiva.

Ahora, aplica $f^{-1}$ en ambos lados, y se obtiene que $n+1 > f(n)$ , $\forall n \in \mathbb{N}$ .

Evidentemente, si $ \forall n \in \mathbb{N}$ , $f(n) = a*n+b$ donde $a \neq 1$ y $b \neq 0$ entonces sería contradictorio $n+1 > f(n)$ , $\forall n \in \mathbb{N}$ .

Ahora sólo queda ver qué pasa si existe un $n'$ donde $f(n') \neq n'$ . En tal caso, $f(n')>n'$ ou $f(n')<n'$ . Comprueba que ambos casos siguen dando lugar a contradicciones.

Creo que si de alguna manera se puede descartar que $f$ está disminuyendo, entonces esto podría funcionar.