# Covergence of the Sequence $b_{k+1} = \frac{1}{3- b_k}$

I'm working with a sequence $(b_{k})_{k=0}^{\infty}$ that is given by $b_{0}=2$ and $b_{k+1}=\frac {1} {3-b_{k}}$ for $k\geq0$. I have to show that the sequence converges and then calculate $\lim_{k \to \infty} b_{k}$. I started by calculating some of the terms: \begin{align*} b_{0}&=2\\ b_{1}&=1\\ b_{2}&=\frac12\\ b_{3}&=\frac25\\ b_{4}&=\frac{5}{13}\\ b_{5}&=\frac{13}{34}\\ b_{6}&=\frac{34}{89}\\ b_{6}&=\frac{89}{233}\\ &\vdots \end{align*}

I initially confused sequence for series. Now I am unsure of how to procede. I can see that the numbers are decreasing, and approaching something around $.3819$.

-
Prove that the sequence is decreasing and bounded below; this will show that it has a limit. Then you can use the usual trick of taking limits on both sides of the recursion to find what the limit is. –  Arturo Magidin Mar 8 '12 at 5:57
You may have noticed the Fibonacci numbers all over the place. –  André Nicolas Mar 8 '12 at 5:57
Sorry I was confusing sequence with series. This is a recurrence relation. I should be trying to induction? Should I edit my original question? –  fitzgeraldo Mar 8 '12 at 6:00
@fitzgeraldo You can edit since the main statement is not correct. Just for you to check, the limit should be $2-\phi$. –  Pedro Tamaroff Mar 8 '12 at 6:04
I fixed the question. You can do it by induction if you want. –  Arturo Magidin Mar 8 '12 at 6:15

You have a sequence, not a series, so your displayed line should read

$$(b_k)_{k=0}^\infty=\left(2,1,\frac12,\frac25,\frac5{13},\frac{13}{34},\frac{34}{89},\frac{89}{233},\,\dots\right)\;.$$

The first step in a problem like this is generally to discover what the limit is, assuming that it exists. There is a rather standard approach that works in most such problems. Let $$f(x)=\frac1{3-x}\;,$$ so that the recurrence is $b_{k+1}=f(b_k)$. The function $f$ is continuous except at $x=3$; let’s assume for the moment that we’ll never have to worry about that discontinuity. Let’s further assume that the sequence has a limit, say $L$. Now take limits on both sides of the recurrence: $$L=\lim_{k\to\infty}b_{k+1}=\lim_{k\to\infty}f(b_k)=f\left(\lim_{k\to\infty}b_k\right)=f(L)\;,$$ so $L$ must be a fixed point of the function $f$. Solve $f(x)=x$ to find that $$L=\frac{3\pm\sqrt5}2\;,$$ and it should be clear from your calculated terms that the only possible limit is $$L=\frac{3-\sqrt5}2\;.$$

In this problem one might guess the limit in another way: one might recognize that each of those fractions is the ratio of two Fibonacci numbers. Specifically, it looks very much as if $$b_k=\frac{F_{2k-3}}{F_{2k-1}}\;.$$

In fact this can be proved rather easily by induction: \begin{align*}f\left(\frac{F_{2k-3}}{F_{2k-1}}\right)&=\frac1{3-\frac{F_{2k-3}}{F_{2k-1}}}\\&=\frac{F_{2k-1}}{3F_{2k-1}-F_{2k-3}}\\&=\frac{F_{2k-1}}{2F_{2k-1}+(F_{2k-1}-F_{2k-3})}\\&=\frac{F_{2k-1}}{2F_{2k-1}+F_{2k-2}}\\&=\frac{F_{2k-1}}{F_{2k-1}+(F_{2k-1}+F_{2k-2})}\\&=\frac{F_{2k-1}}{F_{2k-1}+F_{2k}}\\&=\frac{F_{2k-1}}{F_{2k+1}}\;. \end{align*}

It’s well-known that $$\lim_{k\to\infty}\frac{F_{k+1}}{F_k}=\varphi\triangleq\frac12(1+\sqrt5)\;,$$ so

\begin{align*}\lim_{k\to\infty}\frac{F_{2k-3}}{F_{2k-1}}&=\lim_{k\to\infty}\left(\frac{F_{2k-3}}{F_{2k-2}}\cdot\frac{F_{2k-2}}{F_{2k-1}}\right)\\ &=\lim_{k\to\infty}\frac{F_{2k-3}}{F_{2k-2}}\cdot\lim_{k\to\infty}\frac{F_{2k-2}}{F_{2k-1}}\\ &=\lim_{k\to\infty}\left(\frac{F_{2k-2}}{F_{2k-3}}\right)^{-1}\cdot\lim_{k\to\infty}\left(\frac{F_{2k-1}}{F_{2k-2}}\right)^{-1}\\ &=\varphi^{-1}\cdot\varphi^{-1}\\ &=\varphi^{-2}\;, \end{align*}

which is easily evaluated as $\frac12(3-\sqrt5)$.

Of course this only tells you what the limit must be IF it exists; you still have to prove that the sequence actually converges. This, however, is fairly straightforward, now that we know what the limit is. If you evaluate your first few terms as decimals, you’ll find that they are decreasing and larger than $\frac12(3-\sqrt5)$. You know that every bounded monotone sequence converges, so the natural thing to try is to show that $$\frac12(3-\sqrt5)<b_{k+1}<b_k\tag{1}$$ for all $k\ge 0$. The natural way to prove something like this is by induction on $k$.

Suppose that $(1)$ is true. Then

$$\frac1{3-\frac12(3-\sqrt5)}<\frac1{3-b_{k+1}}<\frac1{3-b_k}\;,$$ so

$$\frac2{3+\sqrt5}<b_{k+2}<b_{k+1}\;.$$

Finally, it’s easy to work out that $$\frac2{3+\sqrt5}=\frac12(3-\sqrt5)\;,$$ so we have $$\frac12(3-\sqrt5)<b_{k+2}<b_{k+1}\;,$$ and it follows by induction that $(1)$ is indeed true for all $k\ge 0$.

Thus, the sequence must converge, and we already know what the limit must be.

(I actually worked a little harder here than was necessary: instead of $(1)$, we could simply have proved that $0<b_{k+1}<b_k$ for all $k\ge 0$. That would still show that the sequence is monotone decreasing and bounded, and it would have saved a little work in the induction step, since it’s clear that if $x<3$, $f(x)>0$.)

-
Would vote up, but I ran out of votes today. –  Pedro Tamaroff Mar 8 '12 at 6:57
Also, why did you put $\mathop = \limits^{\triangle}$? –  Pedro Tamaroff Mar 8 '12 at 6:57
@Peter: Because that’s the definition of $\varphi$. Many people use $:=$ instead, but I prefer $\triangleq$. –  Brian M. Scott Mar 8 '12 at 7:09
I see. I use $:=$. –  Pedro Tamaroff Mar 8 '12 at 7:22

Since no one seems to be willing to actually add an answer.

We can give a formula for your sequence.

If $f_n$ is the $n^{th}$ Fibonacci number, then we have that

$3f_{n+2} - f_n = f_{n+4}$.

Your sequence can be written as $\dfrac{f_{n}}{f_{n+2}}$

Since $\dfrac{f_{n+1}}{f_n} \to \varphi$, the limit of your sequence is $\varphi^{-2}$.

$\varphi$ is the golden ratio.

-

This is just an informal idea.

Pick a large $k=m+n$. You can show that

$${b_{n + m}} = \frac{1}{{3 - \dfrac{1}{{3 - \dfrac{1}{{3 - \cdots \dfrac{1}{{3 - \dfrac{1}{{3 - {b_m}}}}}}}}}}}$$ where there are $n$ threes. This might be used to show that $$\mathop {\lim }\limits_{k \to \infty } {b_k} = \dfrac{1}{{3 - \dfrac{1}{{3 - \dfrac{1}{{3 - \dfrac{1}{{3 - \dfrac{1}{{3 - \cdots }}}}}}}}}}$$

You can then show that smallest root $\ell<1$ of the equation, with $n>1$

$$\ell^2-n\ell+1=0$$

is $$\ell_2 = \frac{n-\sqrt{n^2-4}}{2}$$

The equation itself gives one expansion:

$$\ell_1 = n - \dfrac{1}{{n - \dfrac{1}{{n - \dfrac{1}{{n - \cdots }}}}}}$$

But this will be greater than $1$ (this is the other root). Since we have that

$${\ell _2} = n - {\ell _1}$$

the smaller root has to be

$${\ell _1} = \dfrac{1}{{n - \dfrac{1}{{n - \dfrac{1}{{n - \cdots }}}}}}$$

Your is the special case $n=3$.

-

Assume there is a fixed point, call it $b$. Since it's a fixed point you replace $b_k$ with $b$ to obtain $b = \frac{1}{3-b}$. Solve for $b$. As you noted, the sequence is decreasing, so it will tend towards the smaller of the two solutions.

-

Assume $\omega=1/(3-\omega)$ and $0\lt\omega\lt1$. Note that such a number $\omega$ exists since the function $x\mapsto x-1/(3-x)$ is continuous on $[0,1]$, negative at $x=0$ and positive at $x=1$. Then, $$b_{k+1}-\omega=\frac1{3-b_k}-\frac1{3-\omega}=c_k\cdot(b_k-\omega),$$ with $$c_k=\frac1{(3-b_k)(3-\omega)}.$$ In particular, for every $0\leqslant b_0\leqslant2$, $0\lt c_k\leqslant1/4$ for every $k$ hence $b_k\to\omega$ when $k\to\infty$, the convergence is monotonous (increasing if $b_0\lt\omega$, decreasing if $b_0\gt\omega$) and its rate is at least geometric. In fact, $c_k\to1/(3-\omega)^2=\omega^2$ hence $b_k=\omega+\omega^{2k+o(k)}$ and a little more work would yield $b_k=\omega+C(b_0)\cdot\omega^{2k}\cdot(1+o(1))$.

-