- $F(4n)=F(2n)+F(n)$,
- $F(4n+2)=F(4n)+1$,
- $F(2n+1)=F(2n)+1$
Probar que para cada entero positivo $m$, el número de enteros $n$ con $0 \leq n \leq 2^m$ y $F(4n)=F(3n)$ es $F(2^{m+1})$
La secuencia $f(1), f(2), f(3), ...$ está definida por
$$f(n)=\frac{1}{n} \left (\left \lfloor \frac{n}{1} \right \rfloor + \left \lfloor \frac{n}{2} \right \rfloor + \cdots + \left \lfloor \frac{n}{n} \right \rfloor \right )$$
- Probar que $f(n+1)$ es menor a $n$ para infinitas n.
- Probar que $f(n+1)$ es mayor a $n$ para infinitas n.
2 comentarios:
Wow Chacón, están bonitos :)
1. Sea $F_x$ el $x$-ésimo número de Fibonacci, donde $F_0=F_1=1$. Entonces, si escribimos a $n$ en base binaria:
$n=\sum_{i=1}^k 2^{a_i}$
mostraré que
$F(n)=\sum_{i=1}^k F_{a_i}$.
Para verlo, usamos inducción fuerte (los casos base son fáciles, pues $F(0)=0$ ya que $F(0)=F(0)+F(0)$ por el 1er hecho) y usamos la fórmula recursiva de Fibonacci.
Ahora, demostraré que $F(3n)=F(4n)$ si y sólo sí $n$ no tiene dos $1$s consecutivos en su expresión binaria. Si $n$ no tiene dos $1$s consecutivos, entonces si
$n=\sum_{i=1}^k 2^{a_i}$,
$2n=\sum_{i=1}^k 2^{a_i+1}$
$3n=\sum_{i=1}^k 2^{a_i}+\sum_{i=1}^k 2^{a_i+1}$
Y en la primera y segunda suma, no habrá sumandos en común, entonces $F(3n)=F(2n)+F(n)=F(4n)$ cumplirá.
Ahora supongamos que $F(3n)=F(4n)=F(n)+F(2n)$. Veamos que, si en la suma de $n$ y $2n$ hubiera un acarreo en la $x$-ésima posición, eso aseguraría que $F(3n) \le F(n)+F(2n) - F_x$. No es trivial, pero es fácil de ver, pues el acarreo eventualmente "terminaría"; y ahí podríamos verificar la desigualdad.
Ahora falta ver que el número de $n$ con $0 \le n < 2^m$ y sin dos $1$s seguidos en binario es $F(2^{m+1})=F_{m+1}$. Se hace con inducción.
Los casos bases son fáciles. Para dar el paso inductivo, nos fijamos en las $n$ que cumplen que acaban en $0$ (que son $F_m$) y las que acaban en $01$ (que son $F_{m-1}$). En total serán $F_{m-1}+F_m=F_{m+1}$.
El segundo creo que es más fácil. Sea $g_m(n)$ el número de múltiplos de $m$ menores o iguales a $n$. Notemos que $g_m$ incrementa por $1$ en los múltiplos de $m$, y se mantiene igual en el resto de los números. Entonces $f(n)=(\sum_m g_m(n))/n$. Entonces, si $d(n)$ es el número de divisores de $n$, vemos también que $f(n) = (\sum_{i=1}^n d(i))/n$ y
$f(n) < f(n+1) \Leftrightarrow$
$(n+1)(\sum g_m(n)) < n(\sum g_m(n+1)) \Leftrightarrow$
$n(\sum (g_m(n+1)-g_m(n)) > \sum g_m(n) \Leftrightarrow$
$d(n+1) > f(n) = (\sum_{i=1}^n d(i))/n$.
Con $n+1$ primo, será menor.
Notemos que la función $d$ no está acotada, entonces si escojo $n$ tal que $d(n+1) > d(j)$ para toda $j (\sum_{i=1}^n d(i))/n$.
Entonces acabo.
Nota: $\sum_m g_m(n+1)-g_m(n)=d(m+1)$ pues cuenta los $m$ en los que la función $g_m$ sube en $n+1$ (que son las $m$ divisoras de $n+1$).
Publicar un comentario