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

Solution 1:

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!)

Solution 2:

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.