Golden iteration

The Endeavour 2025-12-12

The expression

$\sqrt{1 + \sqrt{1 + \sqrt{1 + \cdots}}}$

converges to the golden ratio φ. Another way to say this is that the sequence defined by x₀ = 1 and

$x_{n+1} = \sqrt{x_n + 1}$

for n > 0 converges to φ. This post will be about how it converges.

I wrote a little script to look at the error in approximating φ by x_n and noticed that the error is about three times smaller at each step. Here’s why that observation was correct.

The ratio of the error at one step to the error at the previous step is

$\frac{\sqrt{x + 1} - \varphi}{x - \varphi}$

If x = φ + ε the expression above becomes

$\frac{\sqrt{\varphi + \epsilon + 1} - \varphi}{\epsilon} = \frac{1}{\sqrt{2(3 + \sqrt{5})}} - \frac{\epsilon}{\sqrt{8} (3 + \sqrt{5})^{3/2}} + {\cal O}(\epsilon^2)$

when you expand as a Taylor series in ε centered at 0. This says the error multiplied by a factor of about

$\frac{1}{\sqrt{2(3 + \sqrt{5})}} = 0.309016994\ldots$

at each step. The next term in the Taylor series is approximately −0.03ε, so the exact rate of convergence is a slightly faster at first, but essentially the error is multiplied by 0.309 at each iteration.

The post Golden iteration first appeared on John D. Cook.