La disminución por $\sqrt{n}$ cada vez que

Question

Vamos a empezar con un número $n>1$. Cada vez, cuando tenemos un número $t$ a la izquierda, se sustituya por $t-\sqrt{t}$. Cuántas veces, asintóticamente, en términos de $n$) que necesitamos hacer esto hasta que nuestro número pone por debajo de $1$?

Es evidente que se necesitan más de $\sqrt{n}$ a veces, porque necesitamos exactamente $\sqrt{n}$ veces si reemplazamos $t$ $t-\sqrt{n}$ cada vez. La recurrencia es $f(n)=1+f(n-\sqrt{n})$, pero no estoy seguro de cómo resolverlo.

Answer 1

Para atacar este problema, en primer lugar quisiera dar una buena heurística pasando el problema a un continuo analógica que es más fácil de resolver. Vamos, a continuación, modificar la heurística para dar una prueba formal de nuestro asintótica. En primer lugar, piense en lo que sucede si tenemos en cuenta una secuencia $a_n$ se define como $$a_{n+1}=a_n-\sqrt{a_n}$$ a partir de algunos fija $a_0$. Queremos saber la primera $n$ para los que esto es $1$. Ahora, podemos reescribir esto como: $$\Delta a_n = -\sqrt{a_n}$$ donde $\Delta$ es de los delanteros operador diferencia.

Yo hago esto para sugerir lo siguiente, más fácil paralelo problema: Considere una función de $g(t)$ a partir de con $g(0)=a_0$ y que satisface la ecuación diferencial $$g'(t)=-\sqrt{g(t)}$$ donde sólo hemos intercambiado nuestros delanteros diferencia de un derivado. La solución a esto es fácil. En general, la solución es de la forma $$g(t)=\left(\frac{1}2t-c\right)^2$$ para $c\geq 0$. Entonces, necesitamos la $c^2=a_0$ conseguir $g(0)$ a trabajar fuera así, la solución es: $$g(t)=\left(\frac{1}2t-\sqrt{a_0}\right)^2.$$ Lo que deja en claro que tomará $f$ una duración de $2\sqrt{a_0}$, hasta alcanzar los $0$ (o, equivalentemente, $2\sqrt{a_0}-2$, hasta alcanzar los $1$). Observe que $f$ disminuye estrictamente más lento que el de la secuencia, por lo que estamos seguros en ese frente. Observe que $$g(t+1)-g(t)=\frac{1}4-\sqrt{g(t)}$$ que está cerca de la deseada disminución, pero también decae lentamente. Sin embargo, como ya ha demostrado que se necesitan al menos $\sqrt{a_0}$ pasos y este establece que se necesita en la mayoría de las $2\sqrt{a_0}$ pasos, llegamos a la conclusión de que el número de pasos necesarios es asintótica a $O(\sqrt{a_0})$.

Esto supone implícitamente que ronda las raíces cuadradas o no en absoluto. Sin embargo, si usted acaba de elegir a un "disfrazados" de la versión de $g$ se define como $$g(t)=(\alpha t - \sqrt{a_0})^2$$ en realidad se puede demostrar que el límite del número de medidas adoptadas (independientemente de redondeo o cualquiera limitada alteración en la secuencia)$\sqrt{a_0}$$2$. Para dibujar una prueba de esta primera revisión de algunos "fudge factor" $k$ nos dice que el mayor cambio que vas a encontrar debido al redondeo de las cifras (es decir, $k=1$ trabaja para pisos o techos). El próximo uno considera que si $\alpha>\frac{1}2$ $g(t+1)-g(t)$ menos de $-\sqrt{g(t)}-k$ siempre $f(t)$ es grande. Al $\alpha <\frac{1}2$ $g(t+1)-g(t)$ será de más de $-\sqrt{g(t)}+k$. Teniendo en cuenta que $g$ alcance $1$ tiempo $\frac{1+\sqrt{a_0}}{\alpha}$ nos encontramos con que un par de funciones $g$ dos $\alpha$ $\frac{1}2$ unido el comportamiento de la secuencia cuando se queda en grande (y la secuencia sólo se toma un número finito de pasos para pasar de donde se vuelve demasiado pequeño para nuestros límites para aplicar para llegar a $1$ - esta cantidad finita obviamente desaparece si tenemos un límite de con $\sqrt{a_0}$ en el denominador).