9
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Phira
    May 12 '11 at 18:33
  • 4
    $\begingroup$ 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... $\endgroup$ May 12 '11 at 18:37
  • $\begingroup$ 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]$ $\endgroup$
    – user17762
    May 12 '11 at 18:50
  • $\begingroup$ possible duplicate of Why does this process, when iterated, tend towards a certain number? (the golden ratio?) $\endgroup$
    – Aryabhata
    May 13 '11 at 11:18
  • $\begingroup$ math.stackexchange.com/questions/235578/… $\endgroup$ Apr 20 '13 at 13:19
10
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer, this was very useful too. $\endgroup$
    – Listing
    May 12 '11 at 18:45
9
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you for the answer, writing it as a continued fraction makes things much more obvious $\endgroup$
    – Listing
    May 12 '11 at 18:44
9
$\begingroup$

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]]]}]] 
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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