El problema de la limitación que implican bijective función

Question

Deje $f: \Bbb N^{\star}\to \Bbb N^{\star}$ un bijective funciones tales que existe $$\lim _{n \to \infty} {\frac {f(n)} {n}}.$$ Buscar el valor de este límite.

Me di cuenta de que, si $f(n)=n$, entonces el límite es de $1$. Yo no podía hacer más progresos. Me pueden ayudar?

Answer 1

Deje $f$ ser permutación de $\mathbb{N^*}$. Supongamos que la desigualdad de $f(n) \leq n$ tiene sólo un conjunto finito de números enteros $A$. Deje $m = \max A$,$f \left( [m + 1,\infty) \cap \mathbb{N} \right ) \subset [m + 2,\infty) \cap \mathbb{N}$, lo $f^{-1} (\left \{ 1,m+1 \right \}) \subset \left \{ 1,m \right \}$, lo cual no es posible.

Así $f(n) \over {n}$ $ \leq 1$ tiene infinidad de veces.

Aplicando el mismo razonamiento a$f^{-1}$: $\frac{f^{-1}(n)}{n} \leq 1 $ i.e $f(n) \over {n}$ $ \geq 1$ tiene infinidad de veces.

Dado que el límite existe, $\lim \frac{f(n)}{n} = 1$ .

Answer 2

Deje $L = \lim_{n \to \infty} \frac{f(n)}{n}$. Nota:$L \geq 0$. Considere los siguientes casos:

$L > 1$:

Deje $\epsilon > 0$ ser tal que $L > 1 + \epsilon$. A continuación, $\exists N \in \Bbb N$ tal que $\frac{f(n)}{n} > 1 + \epsilon \quad \forall n \geq N$ $\iff f(n) > (1+\epsilon)n$.

Tome $M > N$ suficientemente grande tal que $\epsilon M > 1 \iff (1 + \epsilon)M > M + 1$. A continuación,$\forall n > M, f(n) > M + 1$, por lo que todos los de $f^{-1}(1), f^{-1}(2), \dots f^{-1}(M + 1)$ debe ser dado por $n_1, n_2, \dots, n_{M+1} \leq M$, pero luego por el pigeon-hole principio, al menos dos de las $n_i$ son iguales, lo cual es una contradicción, como $f$ es un bijection.

$0 \leq L < 1$:

Tome $\epsilon > 0$ tal que $L < 1 - \epsilon$. Proceder de forma similar a la $L > 1$ de los casos. $\exists N \in \Bbb N$ tal que $\frac{f(n)}{n} < 1 - \epsilon \quad \forall n \geq N \iff f(n) < (1-\epsilon)n$. Elija $M > N$ suficientemente grande tal que $\epsilon M > 1 \iff (1-\epsilon)M < M - 1$. A continuación,$\forall n > M, f(n) < M - 1$, pero esto es claramente una contradicción ya que el $f$ es un bijection.

Por lo tanto $L = 1$.

Answer 3

Debido a que este límite es finito, existe $M$ $n_0$ tal que $f(n)/n<M$ todos los $n>n_0$, es decir, está delimitada ae.

Ahora, debido a $f(n)<Mn $ todos los $n>n_0$ $f=O(n)$ y, por definición, el límite de solicitud es el 1 de