<s>[INST] How to explain powers of $(x+1)^{2^n}$ appearing in the Babylonian approximation of $\sqrt x$? I'm working with this iteration used for approximating square roots and trying to see what I can draw out from it, and in doing so I found something very strange  that I can't logically explain. I'm looking for any insight into why this is the case or perhaps a proof of it. The iteration  is as follows:
$$\rho_{n+1}=\frac{(\rho_n)^2+x}{2\rho_n},\rho_0=1$$
which approximates $\sqrt x$
I'll list the first four general results here:
$$\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}$$
The property I spotted was that in all cases, the co-efficients of $(x+1)^{2^n}$ appear in $\rho_n$, with the co-efficients of even powers on the numerator and of odd powers on the denominator of $\rho_n$, in such a way that they snake through the polynomial fractions. For example 
$$(x+1)^8=x^8+8x^7+28x^6+56x^5+70x^4+56x^3+28x^2+8x+1$$ and a comparison with $\rho_3$ shows my point nicely.
I can show the general results as sums of multiples of powers of $(x+1)$ and $x$, e.g.
$$\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)}$$
however I don't know how much use this is in explaining the property I found.
Any ideas will be appreciated.
 [/INST] Possible fixed points of the iteration are $\sqrt x$ and $-\sqrt x$,
this suggests to look at
$$
 \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 \, .
$$
It follows that
$$
 \frac{\rho_n - \sqrt x}{\rho_n + \sqrt x} = \left( \frac{1 - \sqrt x}{1 + \sqrt x} \right)^{2^n} \, .
$$
This implies (quadratic) convergence of $\rho_n$ to $\sqrt x$ because
the fraction on the right-hand side is of absolute value less than one
if $x > 0$.
It also gives the explicit formula
$$
\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
$$
which Lord Shark the Unknown found.
If we expand all expressions using the binomial formula then
all odd powers of $\sqrt x$ cancel in the numerator, and all even
powers of $\sqrt x$ cancel in the denominator. This gives the
expression (first found by achille hui in a now deleted answer):
$$
\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}
$$
where the coefficients of the binomial expansion of $(x+1)^{2^n}$
appear alternatingly in the numerator and denominator.
Note also that this is exactly Newton's method to find a zero
of $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} \, .
$$
</s>