10
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ 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.) $\endgroup$ Oct 17, 2010 at 15:36
  • $\begingroup$ +1 for showing what progress you had made. Qiaochu has the right idea. $\endgroup$ Oct 17, 2010 at 15:46
  • $\begingroup$ @Qiaochu Yuan. You mean as n approaches infinity? Would I do this using a limit, the definition of a limit? $\endgroup$
    – Justin
    Oct 17, 2010 at 16:27
  • 1
    $\begingroup$ If you can prove that $c_{n+1}$ is enough closer to L than $c_n$ is, you are there $\endgroup$ Oct 17, 2010 at 16:42
  • 1
    $\begingroup$ 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. $\endgroup$
    – Aryabhata
    Oct 17, 2010 at 17:03

5 Answers 5

4
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ I don't really understand the algebra here. $\endgroup$
    – Justin
    Oct 17, 2010 at 17:09
  • $\begingroup$ From the first to the second line, he just took the 4/5 to the other side and combined the terms. $\endgroup$ Oct 17, 2010 at 17:13
  • $\begingroup$ 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}$ $\endgroup$
    – Justin
    Oct 17, 2010 at 17:30
  • 1
    $\begingroup$ @Justin: $1/(1+d) - 1 = -d/(1+d)$ $\endgroup$
    – Aryabhata
    Oct 17, 2010 at 17:37
  • 1
    $\begingroup$ @Justin: So you are abandoning your approach of monotonic subsequences? $\endgroup$
    – Aryabhata
    Oct 17, 2010 at 17:56
3
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Proving that they're monotonic isn't enough. $\endgroup$ Oct 17, 2010 at 16:49
  • 1
    $\begingroup$ @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. $\endgroup$
    – Aryabhata
    Oct 17, 2010 at 16:55
  • $\begingroup$ @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= $\endgroup$
    – Justin
    Oct 18, 2010 at 1:48
  • $\begingroup$ @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. $\endgroup$
    – Aryabhata
    Oct 18, 2010 at 3:03
  • $\begingroup$ @Justin: ...and the first hint shows that they are appropriately bounded. $\endgroup$
    – Aryabhata
    Oct 18, 2010 at 4:49
2
$\begingroup$

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.

$\endgroup$
0
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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.) $\endgroup$ Oct 17, 2010 at 22:46

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.