# Why does this process, when iterated, tend towards a certain number? (the golden ratio?)

1. Take any number $x$ (edit: x should be positive, heh)
2. Add 1 to it $x+1$
3. Find its reciprocal $1/(x+1)$
4. Repeat from 2

So, taking $x = 1$ to start:

• 1
• 2 (the + 1)
• 0.5 (the reciprocal)
• 1.5 (the + 1)
• 0.666... (the reciprocal)
• 1.666... (the + 1)
• 0.6 (the reciprocal)
• 1.6 (the + 1)
• 0.625
• 1.625
• 0.61584...
• 1.61584...
• 0.619047...
• 1.619047...
• 0.617647058823..

etc.

If we look at just the "step 3"'s (the reciprocals), we get:

• 1
• 0.5
• 0.666...
• 0.6
• 0.625
• 0.61584...
• 0.619047...
• 0.617647058823..

This appears to always converge to 0.61803399... no matter where you start from. I looked up this number and it is often called "The golden ratio" - 1, or $\frac{1+\sqrt{5}}{2}-1$.

1. Is there any "mathematical" way to represent the above procedure (or the terms of the second series, of "only reciprocals") as a limit or series?
2. Why does this converge to what it does for every starting point $x$?

edit: darn, I just realized that the golden ratio is actually 1.618... and not 0.618...; I edited my answer to change what the result is apparently (golden ratio - 1).

However, I think I could easily make it the golden ratio by taking the +1 "steps" of the original series, instead of the reciprocation steps of the original series:

• 2
• 1.5
• 1.666...
• 1.6
• 1.625
• 1.61584...
• 1.619047...
• 1.617647058823..

which does converge to $\frac{1+\sqrt{5}}{2}-1$

Explaining either of these series is adequate as I believe that explaining one also explains the other.

You are iterating the operation $$x\mapsto\frac1{x+1}.$$ We can represent this in matrix terms. Set $$A=\begin{pmatrix} 0&1\\ 1&1\end{pmatrix}.$$ If $$A \begin{pmatrix} x\\ 1\end{pmatrix} =\begin{pmatrix} y_1\\ z_1\end{pmatrix}$$ then $1/(x+1)=y_1/z_1$. After $n$ iterations one gets $$A^n \begin{pmatrix} x\\ 1\end{pmatrix} =\begin{pmatrix} y_n\\ z_n\end{pmatrix}$$ and $x_n=y_n/z_n$ is got by applying the map $x\mapsto 1/(x+1)$ $n$ times to $x$.

Naturally you won't be surprised to find that the eigenvalues of $A$ are $\tau=\frac12(1+\sqrt5)$ and $\tau=\frac12(1-\sqrt5)$. The eigenvectors are $v=(1\ \tau)^t$ and $w=(1\ \tau')^t$. We can write $$\begin{pmatrix} x\\ 1\end{pmatrix}=av+bw$$ and so $$\begin{pmatrix} y_n\\ z_n\end{pmatrix}=a\tau^n v+b\tau'^nw.$$ Now $\tau>1>|\tau'|$ so that for large $n$, $y_n$ and $z_n$ are very close to $a\tau^n$and $a\tau^{n+1}$ so that $x_n\to\infty$ if $a=0$. The only exception is when $a=0$ which only arises for $x=-\frac12(1+\sqrt5)$. (I bet you didn't test that one!)

• I also bet he didn't test $x=\frac(1-\sqrt{5})$. ;-) Oct 20, 2010 at 7:55
• It's hard to test that $x = -(1+\sqrt{5})/2$ is a fixed point numerically, because it's a repelling fixed point. Oct 20, 2010 at 16:31
• (Just to clarify: My comment refers to an earlier version where there was a typo. It's been corrected now.) Oct 20, 2010 at 17:29
• as I remark in the comments to my answer there are a few other exceptions, namely cases where z_n = 0 for some finite n. Of course one can continue the recursion beyond this if one is willing to work in P^1(R) instead of R... Oct 21, 2010 at 10:24

We want to show that the function $f(x) = \frac{1}{1+x}$ has a unique fixed point to which it converges when iterated on positive $x$. If $x$ is positive, then $f(x)$ is between $1$ and $0$, so $f(f(x))$ is between $1$ and $\frac{1}{2}$. It is not hard to see that in fact $f$ fixes the interval $\left[ \frac{1}{2}, 1 \right]$. Now, for $x, y$ in this interval,

$$\left| \frac{1}{x+1} - \frac{1}{y+1} \right| = \left| \frac{y-x}{(1+x)(1+y)} \right| \le \frac{4}{9} |x - y|$$

so on this interval $f$ satisfies the conditions of the Banach fixed point theorem. The unique fixed point to which everything always converges is the unique solution to $f(x) = x$, which you have already found.

• Note that this argument is extremely general; in the right intervals it applies to many other functions one might idly be tempted to iterate on a calculator... Oct 20, 2010 at 15:09
• Here is another case where the fixed point theorem applies. Oct 20, 2010 at 15:17
• The generality of this answer is pretty striking. It even showed why iterating $f(x) = \sqrt{x+1}$ also tends towards the golden ratio. and...basically every other function I've been trying out on my shiny new hp 35s rpn calculator. Oct 20, 2010 at 16:49
• Maybe it's also worth mentioning what happens for negative x. If x equals -F_{n+1}/F_n for any index n (where F_n is the Fibonacci sequence) then some iterate of x is equal to -1 and the sequence blows up. On the other hand, for x less than -2, f(x) is in (-1, 0] so f(f(x)) is positive. And for x greater than -1.5, f(x) is less than -2. The danger zone is [-2, -1.5] and there is some repelling behavior here away from -phi, in addition to the blowing up; note that on this interval f is expansive rather than contractive. Oct 20, 2010 at 21:42

This was supposed to be an addendum to Hans's comment, but it got too long.

The iteration Justin considered formally generates a continued fraction:

$$\cfrac{1}{1+\cfrac{1}{1+\dots}}$$

and as I mentioned in this answer, the numerators and denominators of the nth convergent of a continued fraction can be computed recursively.

If we apply the formula in that answer to this situation, we get

$$\begin{bmatrix}C_n\\\\D_n\end{bmatrix}=\begin{bmatrix}C_{n-1}\\\\D_{n-1}\end{bmatrix}+\begin{bmatrix}C_{n-2}\\\\D_{n-2}\end{bmatrix}$$

with initial conditions

$$\begin{bmatrix}C_{-1}\\\\D_{-1}\end{bmatrix}=\begin{bmatrix}1\\\\0\end{bmatrix},\qquad \begin{bmatrix}C_{0}\\\\D_{0}\end{bmatrix}=\begin{bmatrix}0\\\\1\end{bmatrix}$$

From here, the setup is now similar to Robin's answer, since the two recursions in fact generate the Fibonacci numbers: $C_n=F_n$ and $D_n=F_{n+1}$

Your continued fraction then is the limit

$$\lim_{n\to\infty}\frac{F_n}{F_{n+1}}$$

and the equivalence to Robin's answer is due to the Binet formula:

$$F_n=\frac{\varphi^n-\left(-\varphi^{-1}\right)^n}{\sqrt{5}}$$

(which in fact can be derived from Robin's answer).

Substituting that into the limit and evaluating gets you the answer.

Here is another way of looking at it.

First consider the special case of starting with $1$.

Consider what happens when $\displaystyle x = \frac{f_n}{f_{n+1}}$ where $f_n$ is the $n^{th}$ fibonacci number.

You get $$\frac{1}{\frac{f_n}{f_{n+1}} + 1} = \frac{f_{n+1}}{f_n + f_{n+1}} = \frac{f_{n+1}}{f_{n+2}}$$

Since $\displaystyle 1 = \frac{f_1}{f_2}$

we see that after $n$ iterations, $\displaystyle x = \frac{f_{n+1}}{f_{n+2}}$

This can be generalized to any other starting value, by using a Fibonacci like sequence, which satisfies the recurrence $\displaystyle a_{n+2} = a_{n+1} + a_{n}$ and choosing appropriate $a_{2}$ and $a_{1}$ so that $\displaystyle \frac{a_1}{a_2}$ is the initial guess for $x$.

The $n^{th}$ value for $x$ will be given by $\displaystyle \frac{a_n}{a_{n+1}}$

The general formula for such sequences is given by $a_{n} = A\alpha^n + B\beta^n$ where $\alpha,\beta$ are roots of $\displaystyle z^2 = z + 1$ and thus the limit of $\displaystyle \frac{a_n}{a_{n+1}}$ can be easily found, which will be one of $1/\alpha$ or $1/\beta$ (which you can also see, by assuming there is a limit $1/L$ and setting $\displaystyle 1/L = \frac{1}{1+1/L}$).

Define the function $f(x) = \frac1{1+x}$ so the process you defined is just going from x to f(x). let $x_0\in\mathbb{R}$ and $x_{i+1} = f(x_i)$ then your claim is that $\lim\; x_i = \frac {1+\sqrt{5}}{2}$. if this series converges then $x = \lim\; x_i = \lim\; f(x_{i-1}) = f( \lim\; x_{i-1} ) = f(x)$ so the limit is $x=\frac{1}{1+x}$ or in other words you have $x^2+x-1=0$. the solutions are $\frac{-1\pm \sqrt{5}}{2}$ this isn't exactly the golden ratio. if you take $\frac1{x-1}$ instead then you'll have it. you still need to find out for which $x_0$ this sequence converges - this could be done using numerical analysis (sorry, I'm a bit rusty on this, so I'll leave this part to someone else).