Inyectividad y sobreyectividad de una función recursiva.

Question

Deje $f:\mathbb{N} \to \mathbb{Q}^+$ define de la siguiente manera :

$$\begin{cases} f(0) = 0 \\ f(2n) = \dfrac{1}{f(n)+1} \\ f(2n+1) = f(n)+1 \end{cases}$$

Se pide demostrar la inyectividad, a continuación, el surjectivity de $f$.

Después de examinar primero los valores tomados por $f$, he demostrado por inducción que $f(2^k)=\dfrac{F_k}{F_{k+1}}$ donde $(F_n)$ es la secuencia de fibonacci. También se observa que si $m$ e $n$ tienen distinta paridad, entonces no podemos tener $f(m) = f(n)$ desde $f(2\mathbb{N}) \subset (0,1)$ e $f(2\mathbb{N}+1) \subset [1,+\infty)$.

Alguna idea sobre cómo terminar la prueba de inyectividad y cualquier pensamiento acerca de surjectivity son bienvenidos.

Gracias

Answer 1

Edit: creo que he conseguido finalizar la prueba de surjectivity, pero una comprobación de validez sería muy apreciada.

Supongamos $n,m > 1$. Como usted dice, $f(n) = f(m)$ implica $m \equiv n \pmod{2}$. En particular, por la definición de $f$ tenemos bien $f(n/2) + 1 = f(m/2)+1$ o $(f((n-1)/2) + 1)^{-1} = (f((m-1)/2)+1)^{-1}$ dependiendo de la paridad de $n$ e $m$.

Tomando inversos en la segunda igualdad, uno puede darse cuenta de que ambas condiciones pueden ser declaró a la vez como

$$ f(n) = f(m) \Rightarrow f(\lfloor n/2 \rfloor) = f(\lfloor m/2 \rfloor). $$

Ahora, supongamos que el $f$ es inyectiva en $\{0, \dots, n\}$. Entonces si $m \in \{0, \dots, n\}$ e $f(n+1) = f(m)$, debe ser que $f(\lfloor n+1/2 \rfloor) = f(\lfloor m/2 \rfloor)$.

Dado que tanto $\lfloor n+1/2 \rfloor$ e $\lfloor m/2 \rfloor$ mentira en $\{0, \dots,n\}$, por hipótesis tenemos que $\lfloor n+1/2 \rfloor = \lfloor m/2 \rfloor$. Por lo tanto

$$ 1 > \left|\frac{n+1}{2} - \frac{m}{2}\right| = \frac{1}{2}(n+1-m) $$

y por lo $n+1-m < 2$ lo que demuestra que $n -1 < m$. Desde $m \leq n$, debería ser $m = n$ pero esto implicaría $n \equiv n+1 \pmod{2}$, una contradicción.

Por tanto, vemos que $f$ es inyectiva en $\{0, \dots, n+1\}$, y de manera inductiva esto demuestra que $f$ es inyectiva en todo el dominio.

Como para surjectivity, considere la posibilidad de

$$ a_0 \in \mathbb{N}_0, \quad a_{k+1} := 2a_{k}+1. $$

Esta secuencia cumple que

$$ f(a_{k+1}) = f(a_k) + 1 = \dots = f(a_0) +k, \etiqueta{1} $$

y así tomar $a_0 = 0$ vemos que $f(\mathbb{N}) \supset \mathbb{N}$. Del mismo modo obtenemos

$$ f(2a_{k}) = \frac{1}{f(a_{k})+1} = \frac{1}{f(a_0) + k-1+1} = \frac{1}{f(a_0)+k}. \etiqueta{2} $$

Una vez más, para $a_0 = 0$ este dice que $\{\frac{1}{k}\}_{k \geq 1 } \subset f(\mathbb{N})$. La ecuación de $(1)$ también nos dice que si queremos resolver la ecuación de $f(j) = p/q$ para $p < q$ natural, a continuación, $f$ es surjective, como cada positivos número racional es de la forma $n + p/q$ con $n,p,q \in \mathbb{N}_0$ e $p < q$. Como usted ha señalado, $j$ tendrá que ser aún.

En otras palabras, podemos reducir el problema a la solución de la ecuación

$$ f(2l) = \frac{p}{p+s} \etiqueta{3} $$

para todos los $p,s \geq 1$ y ya hemos comprobado que esto es solucionable por $p = 1$.

Una vez más, vamos a proceder por inducción: supongamos $(3)$ tiene solución para todos los productos naturales inferiores a $p'$. A continuación,

$$ f(2l) = \frac{p}{p'+s} \ffi \frac{1}{f(l)+1} = \frac{p}{p'+s} \ffi f(l)+1 = \frac{p'+s}{p'} $$

y la reescritura de la última, de forma equivalente, es

$$ p'(f(l)+1) = p'+s \iff p'f(l) + p' = p' +s \iff p ° f(l) = s $$

así que, si $s = p'q + r$ con $r < p'$ tenemos

$$ f(l) = \frac{s}{p'} = p + \frac{r}{p'}. $$

Puesto que, por hipótesis de $f(2l') = r/p'$ tiene una solución (porque $r < p'$) podemos establecer $a_0 = 2l'$ y, a continuación, por $(1)$ es

$$ f(a_{p+1}) = f(a_0) + q = q + f(2l') = q + \frac{r}{p'}. $$

Tomando $l = a_{q+1}$, llegamos a la conclusión de que el paso inductivo, demostrando que $f$ es surjective.

Answer 2

La función está dada en la OEIScomo $\, f(n) = a_n/b_n \,$ donde la secuencia de $a_n$ es OEIS secuencia A245327 y $b_n$es OEIS secuencia A245323. Una interpretación de la par de secuencias de $\,(a_n,b_n)\,$ es que ellos son los pasos en el resta-basado Algoritmo de euclides. Son una variante de el Calkin-Wilf árbol o de Stern-Brocot árbol.

Más precisamente, la recursividad es $\,f(2n+1)=1+f(n),\: f(2n)=1/(1+f(n)).$ Esto significa que si tenemos una racional $\, a/b > 1\,$ luego restamos $1$ de lo que da el $\,f(2n+1)\,$ recursividad paso. Si $\, a/b < 1\,$ , a continuación, tomamos el de la reciprocidad y de restar $1$ de lo que da el $\,f(2n)\,$ recursividad paso. Cada racional reducirse $1 = f(1)$ finalmente y, a continuación, nos detenemos.

Answer 3

En primer lugar mostramos $f$ es inyectiva . . .

Supongamos lo contrario.

Deje $a$ ser el menor entero positivo tal que $|f^{-1}\bigl(f(a)\bigr)| > 1$.

Es fácil ver que $f(n)=1$ si y sólo si $n=1$, por lo tanto $a > 1$.

Deje $b$ ser un entero positivo con $b > a$ tal que $f(a)=f(b)$.

Si $a$ es par, entonces es $b$, por lo tanto \begin{align*} &f(a)=f(b)\\[4pt] \implies\;&\frac{1}{f\left({\large{\frac{a}{2}}}\right)+1}=\frac{1}{f\left({\large{\frac{b}{2}}}\right)+1}\\[4pt] \implies\;&f\left({\small{\frac{a}{2}}}\right)=f\left({\small{\frac{b}{2}}}\right)\\[4pt] \end{align*} contradiciendo la minimality de $a$.

Del mismo modo, si $a$ es impar, entonces es $b$, por lo tanto \begin{align*} &f(a)=f(b)\\[4pt] \implies\;&f\left({\small{\frac{a-1}{2}}}\right)+1=f\left({\small{\frac{b-1}{2}}}\right)+1\\[4pt] \implies\;&f\left({\small{\frac{a-1}{2}}}\right)=f\left({\small{\frac{b-1}{2}}}\right)\\[4pt] \end{align*} de nuevo contradiciendo la minimality de $a$.

Por lo tanto, $f$ es inyectiva.

A continuación se muestra $f$ es surjective . . .

Deje $\mathbb{Z}^{+}$ denota el conjunto de números enteros positivos, y deje $\mathbb{Q}^{+}$ denota el conjunto de los números racionales positivos.

Para $x\in \mathbb{Q}^{+}$, vamos a $w(x)=p+q$, donde $x={\large{\frac{p}{q}}}$, con $p,q\in \mathbb{Z}^{+}$ e $\gcd(p,q)=1$.

Nuestro objetivo es mostrar a $ \mathbb{Q}^{+}\subseteq f(\mathbb{Z}^{+})$.

Supongamos lo contrario.

Elija $x\in \mathbb{Q}^{+}$ tal que $w(x)$ es menor entre todos los elementos de $\mathbb{Q}^{+}$ que no son elementos de $f(\mathbb{Z}^{+})$.

Escribir $x={\large{\frac{p}{q}}}$, donde $p,q\in \mathbb{Z}^{+}$ e $\gcd(p,q)=1$.

Desde $f(1)=1$, se deduce que el $p\ne q$.

Si $p < q$, luego por minimality de $w(x)$, tenemos $$f(n)=\frac{q-p}{p}$$ para algún entero positivo $n$, por lo tanto $$f(2n)=\frac{1}{f(n)+1}=\frac{1}{{\large{\frac{q-p}{p}}}+1}=\frac{p}{q}$$ contradicción.

Del mismo modo, si $p > q$, luego por minimality de $w(x)$, tenemos $$f(n)=\frac{p-q}{q}$$ para algún entero positivo $n$, por lo tanto $$f(2n+1)=f(n)+1=\frac{p-q}{q}+1=\frac{p}{q}$$ contradicción.

De ello se desprende que $f$ es surjective.