# Prove that the sequence$c_1 = 1$, $c_{n+1} = 4/(1 + 5c_n)$ , $n \geq 1$ is convergent and find its limit

Prove that the sequence $c_{1} = 1$, $c_{(n+1)}= 4/(1 + 5c_{n})$ , $n \geq 1$ is convergent and find its limit.

Ok so up to now I've worked out a couple of things.
$c_1 = 1$
$c_2 = 2/3$
$c_3 = 12/13$
$c_4 = 52/73$

So the odd $c_n$ are decreasing and the even $c_n$ are increasing. Intuitively, it's clear the the two sequences for odd and even $c_n$ are decreasing/increasing less and less. Therefore it seems like the sequence may converge to some limit $L$.

If the sequence has a limit, let $L=\underset{n\rightarrow \infty }{\lim }a_{n}.$ Then $L = 1/(1+5L).$ So we yield $L = 4/5$ and $L = -1$. But since the even sequence is increasing and >0, then $L$ must be $4/5$.

Ok, here I am stuck. I'm not sure how to go ahead and show that the sequence converges to this limit (I tried using the definition of the limit but I didn't manage) and and not sure about the separate sequences how I would go about showing their limits.

A few notes : I am in 2nd year calculus. This is a bonus question, but I enjoy the challenge and would love the extra marks. Note : Once again I apologize I don't know how to use the HTML code to make it nice.

-
Try showing that c_n - L tends to zero. That is usually easier. (Overkill solution: the sequence c_n actually has a closed form, but I don't think you'll need to use this.) – Qiaochu Yuan Oct 17 '10 at 15:36
+1 for showing what progress you had made. Qiaochu has the right idea. – Ross Millikan Oct 17 '10 at 15:46
@Qiaochu Yuan. You mean as n approaches infinity? Would I do this using a limit, the definition of a limit? – fdart17 Oct 17 '10 at 16:27
If you can prove that $c_{n+1}$ is enough closer to L than $c_n$ is, you are there – Ross Millikan Oct 17 '10 at 16:42
Guys, I suggest you try to 'unstuck' OP rather than throwing different methods at him. Once OP has solved it, throw as much as you want :-) Just my 2c. – Aryabhata Oct 17 '10 at 17:03

Well done! Your observations are correct and can be completed to give a proof that the sequence is convergent to $\frac{4}{5}$.

The tough part in proving your observations it to prove that the odd/even sub-sequences are monotonic and appropriately bounded (what do I mean by this?).

Here is a hint:

Show that $$c_{2n-1} \ge \frac{4}{5} \ge c_{2n} \ \ \forall n \ge 1$$

Hint2:

Try writing $\displaystyle c_{n+2}$ in terms of $\displaystyle c_{n}$ and see if that helps you prove the above bounds (and as a next step, the monotonicity).

(For a simpler proof of the above bound, you can also try showing that if $c_{n} \ge 4/5$ then $c_{n+1} \le 4/5$ and similarly if $c_n \le 4/5$ then $c_{n+1} \ge 4/5$).

-
Proving that they're monotonic isn't enough. – Qiaochu Yuan Oct 17 '10 at 16:49
@Qiaochu: Of course it isn't. Isn't it obvious that this is incomplete? It can be completed to give the full proof, though. I was only trying to nudge OP in the direction of their own thinking, which is actually enough to solve this problem. – Aryabhata Oct 17 '10 at 16:55
+1 for following the OP approach. – Nuno Oct 17 '10 at 19:28
@Moron Ok so I have shown that for $c_n >= 4/5, c_{n+1} <= 4/5$ But for c_n <= 4/5, I need to show that c_n is bounded below first right? Again I'm stuck D= – fdart17 Oct 18 '10 at 1:48
@Justin: Not sure what you mean. If you show the statement I said in brackets then your have proved the first hint. Using that now you can try to show that the even terms subsequence is monotonically increasing and the odd terms subsequence is monotonically decreasing, like you observed. – Aryabhata Oct 18 '10 at 3:03

Here is a more explicit version of my hint. I said it would be easier to show that $d_n = c_n - \frac{4}{5}$ tends to zero as $n \to \infty$. This gives $d_1 = \frac{1}{5}$ and the recurrence

$$d_{n+1} + \frac{4}{5} = \frac{4}{1 + 5(d_n + \frac{4}{5})} = \frac{4}{5} \frac{1}{1 + d_n}$$

hence

$$d_{n+1} = - \frac{4}{5} \frac{d_n}{1 + d_n}.$$

Can you see what to do from here?

Edit: Some more hints. If the $1 + d_n$ in the denominator were just a $1$, we would be done because then $|d_n|$ would decrease exponentially at least as fast as $\left( \frac{4}{5} \right)^n$. But it's not. However, $d_n$ is small, so the denominator should be close enough to $1$ that this argument should still go through. More precisely, you just need to find a constant $0 < c < \frac{1}{5}$ such that you can prove that $|d_n| \le c$, say for $n \ge 2$. (Maybe by induction.) From there it will follow that $|d_n|$ actually decays exponentially at least as fast as $\left( \frac{4}{5(1 - c)} \right)^n$.

This is an example of a general technique called "bootstrapping," where you use weak estimates together with relations that a sequence satisfies to get stronger estimates.

-
I don't really understand the algebra here. – fdart17 Oct 17 '10 at 17:09
From the first to the second line, he just took the 4/5 to the other side and combined the terms. – Paul VanKoughnett Oct 17 '10 at 17:13
Huh? How does he go from the rightmost equality on Line 1 to Line 2. it should be. $\frac{4}{5} * \frac{1}{1 + d_n} - \frac{4}{5}$ – fdart17 Oct 17 '10 at 17:30
@Justin: $1/(1+d) - 1 = -d/(1+d)$ – Aryabhata Oct 17 '10 at 17:37
@Justin: So you are abandoning your approach of monotonic subsequences? – Aryabhata Oct 17 '10 at 17:56

As shown by the other answers, there are a few nice ways to approach this problem.

You could concentrate only on $C_{2n-1},$ say, since if you establish that $C_{2n-1}$ tends to a limit you automatically nail $C_{2n}$ as well, because

$$C_{2n} = \frac{4}{1+5C_{2n-1}} \textrm { so } \lim C_{2n} = \lim \frac{4}{1+5C_{2n-1}}.$$

Now it's easy to show $C_{2n-1} > 4/5$ and so expand $$(5C_{2n-1}-4)(C_{2n-1}+1)>0$$

and manipulate (add $20C_{2n-1}$ to both sides and take the 4 to the RHS) to obtain

$$C_{2n-1} > \frac{4+20C_{2n-1}}{21+5C_{2n-1}} = C_{2n+1},$$

and since $C_{2n-1}$ is bounded below by 4/5 the result follows immediately.

-

Here's one way to prove it: let $f(x) = 4/(1+5x)$. Say $|x-4/5| \le C$ for some constant $C$. Can you find $C$ and some constant $0 \le k < 1$ so that if $|x-4/5| \le C$, then $|f(x)-4/5| \le k|x-4/5|$?

If you do this, then you can iterate to get $|f^j(x)-4/5| \le k^j |x-4/5|$, for all $j$, and so if you make $j$ large enough then you can get $f^j(x)$ as close to $4/5$ as you like.

-

So $c_{1} = 1$ and $c_{n+1} = 4/(1+5c_{n})$ for $n \geq 1$. Let $C(x) = \sum_{n \geq 1} c_{n}x^n$. Then maybe try to express $\sum_{n \geq 1} c_{n+1}x^n$ and $\sum_{n \geq 1} \frac{4x^n}{1+5c_{n}}$ in terms of $C(x)$ to get a closed form.

-
You won't get a closed form this way. If you want a closed form, think about the fact that composition of fractional linear transformations corresponds to matrix multiplication and diagonalize the associated matrix. (I say this as a service to anyone interested in the closed form and not to the OP, who I am guessing does not know enough linear algebra for this to be helpful.) – Qiaochu Yuan Oct 17 '10 at 22:46