Cómo explicar los poderes de $(x+1)^{2^n}$ que aparece en la aproximación babilónica de $\sqrt x$ ?

Question

Estoy trabajando con esta iteración utilizada para aproximar raíces cuadradas y tratando de ver qué puedo sacar de ella, y al hacerlo he encontrado algo muy extraño que no puedo explicar lógicamente. Estoy buscando alguna idea de por qué esto es así o quizás una prueba de ello. La iteración es la siguiente:

$$\rho_{n+1}=\frac{(\rho_n)^2+x}{2\rho_n},\rho_0=1$$ que se aproxima a $\sqrt x$

Enumeraré aquí los cuatro primeros resultados generales:

$$\rho_1=\frac{x+1}{2}$$ $$\rho_2=\frac{x^2+6x+1}{4x+4}$$ $$\rho_3=\frac{x^4+28x^3+70x^2+28x+1}{8x^3+56x^2+56x+8}$$ $$\rho_4=\frac{x^8+120x^7+1820x^6+8008x^5+12870x^4+8008x^3+1820x^2+120x+1}{16x^7+560x^6+4368x^5+11440x^4+11440x^3+4368x^2+560x+16}$$

La propiedad que detecté fue que en todos los casos, los coeficientes de $(x+1)^{2^n}$ aparecen en $\rho_n$ con los coeficientes de las potencias pares en el numerador y de las potencias Impares en el denominador de $\rho_n$ de tal manera que serpentean a través de las fracciones del polinomio. Por ejemplo $$(x+1)^8=x^8+8x^7+28x^6+56x^5+70x^4+56x^3+28x^2+8x+1$$ y una comparación con $\rho_3$ muestra muy bien mi punto de vista.

Puedo mostrar los resultados generales como sumas de múltiplos de potencias de $(x+1)$ y $x$ Por ejemplo $$\rho_2=\frac{(x+1)^2+4x}{4(x+1)}$$ $$\rho_3=\frac{(x+1)^4+24x(x+1)^2+16x}{8(x+1)^3+32x(x+1)}$$

sin embargo no se que utilidad tiene esto para explicar la propiedad que encontré.

Cualquier idea será apreciada.

Answer 1

De estas fórmulas se desprende que $$\rho_n=\frac{(\sqrt x+1)^{2^n}+(\sqrt x-1)^{2^n}} {(\sqrt x+1)^{2^n}-(\sqrt x-1)^{2^n}}\sqrt x$$ y una vez que se tiene esa fórmula, se puede verificar por inducción.

Answer 2

Los posibles puntos fijos de la iteración son $\sqrt x$ y $-\sqrt x$ , esto sugiere mirar $$ \frac{\rho_{n+1} - \sqrt x}{\rho_{n+1} + \sqrt x} = \frac{\rho_n^2 - 2 \sqrt x \rho_n + x}{\rho_n^2 + 2 \sqrt x \rho_n + x} = \left( \frac{\rho_n - \sqrt x}{\rho_n + \sqrt x} \right)^2 \, . $$ De ello se desprende que $$ \frac{\rho_n - \sqrt x}{\rho_n + \sqrt x} = \left( \frac{1 - \sqrt x}{1 + \sqrt x} \right)^{2^n} \, . $$ Esto implica la convergencia (cuadrática) de $\rho_n$ a $\sqrt x$ porque la fracción del lado derecho tiene un valor absoluto menor que uno si $x > 0$ . También da la fórmula explícita $$ \rho_n=\frac{(\sqrt x+1)^{2^n}+(\sqrt x-1)^{2^n}} {(\sqrt x+1)^{2^n}-(\sqrt x-1)^{2^n}}\sqrt x $$ que Señor Tiburón el Desconocido encontrado .

Si expandimos todas las expresiones utilizando la fórmula binomial entonces todas las potencias Impares de $\sqrt x$ se cancelan en el numerador, y todas las potencias de $\sqrt x$ se cancelan en el denominador. Esto da la expresión (encontrada por primera vez por achille hui en una respuesta ahora borrada): $$ \rho_n = \frac{\sum_{k=0}^{2^{n-1}} \binom{2^n}{2k} x^k}{\sum_{k=0}^{2^{n-1}}\binom{2^n}{2k+1} x^k} $$ donde los coeficientes de la expansión binomial de $(x+1)^{2^n}$ aparecen alternativamente en el numerador y el denominador.

Tenga en cuenta también que esto es exactamente Método de Newton para encontrar un cero de $f(\rho) = \rho^2 - x$ : $$ \rho_{n+1} = \rho_n - \frac{f(\rho_n)}{f'(\rho_n)} = \rho_n - \frac{\rho_n^2 - x}{2 \rho_n} = \frac{\rho_n^2 + x}{2 \rho_n} \, . $$