Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
  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.

share|improve this question
1  
One can note that this process is exactly what's behind the nice form of the continued fraction expansion of the golden ratio: en.wikipedia.org/wiki/Golden_ratio#Alternate_forms –  Hans Lundmark Oct 20 '10 at 8:07
add comment

5 Answers

up vote 13 down vote accepted

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.

share|improve this answer
1  
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... –  Qiaochu Yuan Oct 20 '10 at 15:09
1  
Here is another case where the fixed point theorem applies. –  J. M. Oct 20 '10 at 15:17
    
+1: For talking about Banach's fixed point theorem. –  Aryabhata Oct 20 '10 at 16:32
1  
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. –  Justin L. Oct 20 '10 at 16:49
1  
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. –  Qiaochu Yuan Oct 20 '10 at 21:42
add comment

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

share|improve this answer
2  
I also bet he didn't test $x=\frac(1-\sqrt{5})$. ;-) –  Hans Lundmark Oct 20 '10 at 7:55
1  
It's hard to test that $x = -(1+\sqrt{5})/2$ is a fixed point numerically, because it's a repelling fixed point. –  Michael Lugo Oct 20 '10 at 16:31
1  
(Just to clarify: My comment refers to an earlier version where there was a typo. It's been corrected now.) –  Hans Lundmark Oct 20 '10 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... –  Qiaochu Yuan Oct 21 '10 at 10:24
add comment

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.

share|improve this answer
add comment

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}$).

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.