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.

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.

share|improve this question
1  
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
    
Just put dollar signs around your formulas and they will look fine! Instead of >=, write "\ge", and to get $c_{n+1}$, write "c_{n+1}" with curly brackets. –  Hans Lundmark 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
1  
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
1  
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

5 Answers 5

up vote 3 down vote accepted

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

share|improve this answer
    
Proving that they're monotonic isn't enough. –  Qiaochu Yuan Oct 17 '10 at 16:49
1  
@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.

share|improve this answer
    
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
1  
@Justin: $1/(1+d) - 1 = -d/(1+d)$ –  Aryabhata Oct 17 '10 at 17:37
1  
@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.

share|improve this answer
    
Did you notice the homework tag? meta.math.stackexchange.com/questions/914/…. Disclaimer: I am only trying to make sure you are aware of the guidelines and not trying to force you to follow them. –  Aryabhata Oct 17 '10 at 20:18
    
Actually, I didn't see the homework tag in this case, probably because I'm still coughing and spluttering my way through the end of a very nasty cold and only popped over for a few minutes to see what was happening. I do think they are reasonable guides, though. –  Derek Jennings Oct 17 '10 at 21:17

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.

share|improve this answer

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.

share|improve this answer
    
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

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.