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.

We define

$$a_{n+1}=\frac{1}{1+a_n}, a_0=c> 0$$

I stumbled across that sequence and Mathematica gives me that it converges against $\frac{1}{2} \left(\sqrt{5}-1\right)$ which doesn't even depend on $a_0$. Normally I show that sequences converge by seeing that they are monotonic and then the limit can be easily found by setting $a_n=a_{n+1}$, but this one seems to be alternating. Also by checking OEIS I noticed that $a_n=1/g(n)$ where $g(n)$ gives the $n+1$'th Golden Rectangle Number.

I would be glad if someone can show me how to show that such sequences converge and how to find the limit, also maybe this is a well known sequence, as it has a quite simple form, too bad that google is very bad for looking for sequences and OEIS doesn't mention anything.

share|improve this question
    
These numbers are the convergents of the continued fraction of the golden ratio. If you assume that it converges you can calculate the limit by replacing the $a_k$s by $a$. You can prove convergence by proving that the odd/even subsequences are monotonous. –  Phira May 12 '11 at 18:33
4  
Right, but 3123 is asking why $\frac{\sqrt{5}-1}{2}$ is a(n attractive) fixed point of the function $f(x)=\frac1{a+x}$ for "any" starting value... –  J. M. May 12 '11 at 18:37
    
The reason why $a_n$ converges to a fixed value irrespective of $a_0 = c$ is actually not really surprising. For instance, consider $a_0 = \frac{c}{10}$ where $c \in [0,10]$ $a_{n+1} = \frac{9+a_n}{10}$ Note that $\displaystyle \lim_{n\rightarrow \infty} a_n = 1$ for any starting value $c \in [0,10]$ –  user17762 May 12 '11 at 18:50
    
    

3 Answers 3

up vote 8 down vote accepted

As for why the first term does not matter, consider the $6$th term,

$$\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+c}}}}}$$

as $c$ varies between $0$ and $\infty$ the value of the $6$th term varies only by $0.1$. As $c$ varies between $0$ and $\infty$ the $100$th term varies only by very small $\varepsilon$. In the infinite limit this variation is zero.

This also explains convergence. Since convergence occurs call the number $\varphi$, it satisfies the fixed point equation

$\varphi = \frac{1}{1+\varphi}$

which, multiplying both sides by the denominator, is a quadratic equation hence the square root.

share|improve this answer
    
Thank you for the answer, writing it as a continued fraction makes things much more obvious –  Listing May 12 '11 at 18:44

For $x\geq 0$, $f(x)=1/(1+x)$ is a monotonically decreasing function, bounded between 0 and 1. The fixed point (if it exists) of the iterative map defined by your function, is the solution of $x=\frac{1}{1+x}$. There is only one solution for $x\geq 0$, and that is $\tilde{x}=(\sqrt{5}-1)/2$.

If we look at the evolution of $a_n=f(f(f(...(a_0))))$, we get

$$a_n=\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+a_0}}}}}$$

and as $n\to\infty$, what $a_0$ was becomes irrelevant. In other words, no matter the value of $a_0$, it converges to a fixed point, which has to be the only fixed point, $\tilde{x}$. Hence $\tilde{x}$ is an attractive fixed point and also the limit of the sequence.

enter image description here

The Mathematica code that produced the above figure is below (it's modified from an answer to a question on SO)

Clear[fixedPoint]
fixedPoint[a0_, nSteps_] := 
 Module[{f, a, n}, 
  f = RecurrenceTable[{a[n] == 1/(1 + a[n - 1]), a[1] == a0}, 
    a, {n, 1, nSteps}];
  Plot[{1/(1 + x), x}, {x, 0, 1}, 
   PlotStyle -> {Darker@Blue, {Dashed, Black}}, 
   Epilog -> {Darker@Green, 
     Line[Riffle[Partition[f, 2, 1], {#, #} & /@ Rest[f]]]}]] 
share|improve this answer

The function $1/(1+x)$ is strictly decreasing and thus order-reversing on the positive reals. If you apply it twice it conserves order.

Therefore, the odd and even subsequences are monotonic. They are also bounded as all your values except the first are bounded by 1.

Now you can just replace $a_n$ and $a_{n+1}$ by $a$ to find the limit.

share|improve this answer
    
Thank you for your answer, this was very useful too. –  Listing May 12 '11 at 18:45

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.