Calculating the Golden Ratio

Here I’ll exhibit a method from approximating another well known irrational. The Golden Ratio, often denoted \varphi, has fascinated people for many years, some going as far as to attribute mystical connotations to it.

\varphi crops up a lot in nature and it’s always a pleasure to see it. It’s most easily understood as the positive root of the quadratic x^2-x-1, making it equal to \frac{1+\sqrt{5}}{2} . Note that this means it has the property \varphi^2 = \varphi + 1. This time we’ll construct a sequence converging to \varphi using the function f(x) = 1 + \frac{1}{x} .

Let x_0 = 1, and for all n\in\mathbb{N} let x_{n+1} = f(x_n). Then the first few numbers in this sequence are

1,2,\frac{3}{2},\frac{5}{3},\frac{8}{5},\frac{13}{8},...

One might begin to suspect at this point that x_n = \frac{F_{n+1}}{F_n}, where \{F_n\} is the Fibonacci sequence (with F_0 =  F_1 = 1). We can prove this is the case by induction, we’ve already shown the base case by listing the first few values above. Then if we assume that for some k\in\mathbb{N} x_k = \frac{F_{k+1}}{F_k}, then

\begin{array}{ccl} x_{k+1} &=& f(x_k)\\&=& 1+\frac{1}{x_k}\\ &=& \frac{F_{k+1} + F_k}{F_{k+1}}\\&=& \frac{F_{k+2}}{F_{k+1}}\end{array} .

This sequence is known to converge to \varphi, but I’ve never explicitly convinced myself of this before so I’ll do that now. First we’ll define a new sequence \{y_n\} by y_n = x_{n+1}. In doing so we’ve ditched the first element of the sequence and so now for all n\in\mathbb{N}, 1.5\leq y_n \leq 2. This is because for all x we have that 1.5\leq x\leq 2 implies 1.5\leq f(x)\leq 2, which you can check out for yourself. Now we note that for all 1.5\leq x,y \leq 2 we have

\begin{array}{ccl} |f(x)-f(y)| &=& |\frac{1}{x}-\frac{1}{y}|\\&=& \frac{1}{xy}|x-y| \\ &\leq& \frac{4}{9}|x-y|\end{array} ,

since \frac{1}{xy} achieves a maximum of \alpha = \frac{4}{9} on the square [1.5,2]\times [1.5,2].

(This shows that f(x) is a contraction mapping on the interval 1.5\leq x\leq 2. At this point we could appeal to the Banach fixed-point theorem and we’d be done. Instead, we directly prove convergence of our series using some inspiration from that theorem).

The next thing we can so is derive the following inequality (from here on in we’re assuming that all numbers we consider are between 1.5 and 2):

\begin{array}{cccl} &|x-y| &\leq& |x-f(x)| + |f(x)-f(y)| + |y-f(y)| \\ \Rightarrow&|x-y|& \leq & \frac{1}{1-\alpha}(|x-f(x)|+ |y-f(y)|)\end{array}

Clearly

|y_1-y_0| \leq \alpha^0|y_1 - y_0|.

Now if we assume that for some k, |y_{k+1} - y_k| \leq \alpha^k|y_1-y_0| then

|y_{k+2} - y_{k+1}| = |f(y_{k+1} )- f(y_k)| \leq \alpha^{k+1}|y_1-y_0|.

Thus by induction |y_{n+1}-y_n| \leq \alpha^n|y_1-y_0| for all n.

Now we show this sequence is Cauchy convergent by noting that for all m,n

|y_n - y_m| \leq\frac{1}{1-\alpha}(|y_{n+1}-y_n|+|y_{m+1}-y_m|)\leq \frac{\alpha^n + \alpha^m}{1-\alpha}|y_1 - y_0|

which clearly approaches 0 as m and n go to \infty. So \{y_n\} (and thus \{x_n\}) is Cauchy convergent, and thus convergent since \mathbb{R} is complete. To see that it converges to \varphi, we’ll use the continuity of f(x):

\begin{array}{ccl} \lim_{n\rightarrow \infty}x_{n}&=& \lim_{n\rightarrow \infty}x_{n+1} \\&=& \lim_{n\rightarrow\infty}f(x_n)\\&=& f(\lim_{n\rightarrow\infty}x_n)\end{array}

Since the equation f(x) = x has a unique solution for 1.5\leq x\leq 2, it must be that \lim_{n\rightarrow \infty}x_n = \varphi.

Thus by iterated application of the function f(x) = 1+\frac{1}{x} we may approximate \varphi. Continued iteration yields ever more accurate approximations.

Let me know if I’ve made any mistakes, I haven’t given myself much proof-reading time before publishing (=

 

 

Advertisements