# showing a sequence converges

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Jun 21st 2010, 02:47 AM
bolton_boy
showing a sequence converges
Hey guys,

I have a function y=(x+2)/(x+1) and I have performed iterations to show that for any initial value other than -sqrt{2} the sequence converges to sqrt{2}.

So I have found that sqrt{2} is a stable fixed point and -sqrt{2} is an unstable fixed point.

Now I have to prove my findings using a standard test for convergence?

Can anyone help.
• Jun 21st 2010, 03:01 AM
Ackbeet
Would I be right in considering that you are setting up an iteration scheme as follows:

$y=f(x)=\frac{x+2}{x+1}$,

$x_{n+1}=f(x_{n})$?

In this case, can I ask if you've ever heard of the Banach fixed point theorem?
• Jun 21st 2010, 03:03 AM
bolton_boy
yes that is how I am setting up the scheme, and no I haven't heard of that sorry. The only 'standard' tests we have studied have been things like ratio test, limit theorem test, comparison test, nth term test etc
• Jun 21st 2010, 03:04 AM
Ackbeet
Ok, so what have you tried so far?
• Jun 21st 2010, 03:05 AM
bolton_boy
Most of them to be honest, but none of them seem to work as I can't let n tend to infinity
• Jun 21st 2010, 03:25 AM
bolton_boy
I know that the limits of $s_{n+1}$ and $s_n$ are the same, so I have solved the equation $L=\frac{L+10}{L+1}$ to find the limits to be $\pm \sqrt{10}$
• Jun 21st 2010, 03:59 AM
Ackbeet
Ok, let me just think out loud here for a bit. You've got a sequence

$a_{n+1}=\frac{a_{n}+2}{a_{n}+1}$.

If we think of using the ratio test, we're looking at

$L=\lim_{n\to\infty}\left|\frac{a_{n+1}}{a_{n}}\rig ht|=
\lim_{n\to\infty}\left|\frac{a_{n}+2}{a_{n}+1}\cdo t\frac{1}{a_{n}}\right|$
.

Nothing jumps out. As you said, there's no real way to let $n$ tend to infinity.

In addition, the sequence is not monotone. I just tried the sequence starting out with the number 1, and the sequence oscillated about $\sqrt{2}$.

That gives me one idea: instead of looking at $a_{n+1}=\frac{a_{n}+2}{a_{n}+1}$, let's look at the sequence $a_{n+1}-\sqrt{2}=\frac{a_{n}+2}{a_{n}+1}-\sqrt{2}$. If you can prove the sequence is an alternating sequence, then you could use the alternating series test, perhaps.

Or, here's another idea. Start with $a_{0}$, and see if you can find a general equation of the $n$th term.

We have

$a_{1}=\frac{a_{0}+2}{a_{0}+1}$,

$a_{2}=\frac{a_{1}+2}{a_{1}+1}=\frac{\frac{a_{0}+2} {a_{0}+1}+2}{\frac{a_{0}+2}{a_{0}+1}+1}
=\frac{3a_{0}+4}{2a_{0}+3}$
,

$a_{3}=\frac{a_{2}+2}{a_{2}+1}=\frac{\frac{3a_{0}+4 }{2a_{0}+3}+2}{\frac{3a_{0}+4}{2a_{0}+3}+1}=\frac{ 7a_{0}+10}{5a_{0}+7}$,

$a_{4}=\frac{a_{3}+2}{a_{3}+1}=\frac{\frac{7a_{0}+1 0}{5a_{0}+7}+2}{\frac{7a_{0}+10}{5a_{0}+7}+1}=\fra c{17a_{0}+24}{12a_{0}+17}$.

That's all I have time for right now. What you'd like to do is write the sequence as a function of $a_{0}$ and $n$, but without any $a_{n}$'s in it. If you could do that, you could take the limit.
• Jun 21st 2010, 05:47 AM
bolton_boy
I have just spoken to someone I know, and the easiest way is too show that it is a decreasing sequence bounded below and then it converges to its infimum?
• Jun 21st 2010, 05:55 AM
Ackbeet
It has occurred to me that the original iteration scheme is nonlinear, hence impervious to the z-transform technique. However, it may be that the four numbers that show up in each iteration can be resolved by a linear recurrence relation.

The last step I wrote was

$a_{4}=\frac{17a_{0}+24}{12a_{0}+17}$. The next step would be

$a_{5}=\frac{a_{4}+2}{a_{4}+1}=\frac{\frac{17a_{0}+ 24}{12a_{0}+17}+2}{\frac{17a_{0}+24}{12a_{0}+17}+1 }=\frac{41a_{0}+58}{29a_{0}+41}$.

So you have, it looks like three numbers (two of the numbers appear always to be identical) to determine for each n. Can you set up a recurrence relation that determines each of those numbers?

Incidentally, I would agree that often the bounded monotone sequence converges theorem is a nice one to use. However, it does not apply here, because, as I mentioned above, this sequence is not monotone. It oscillates about $\sqrt{2}$, as it gets closer and closer.

I should also point out that the computations I have done above show that there is an infinite sequence of numbers that is not in the domain of the iteration scheme: those points where all the denominators of various terms in the sequence are equal to zero.
• Jun 21st 2010, 06:34 AM
Ackbeet
So, let's assume the following ansatz:

$a_{n}=\frac{f_{n}a_{0}+g_{n}}{h_{n}a_{0}+f_{n}}$.

Then we have

$
a_{n+1}
=\frac{a_{n}+2}{a_{n}+1}
=\frac{\frac{f_{n}a_{0}+g_{n}}{h_{n}a_{0}+f_{n}}+2 }{\frac{f_{n}a_{0}+g_{n}}{h_{n}a_{0}+f_{n}}+1}
=\frac{\frac{(f_{n}+2h_{n})a_{0}+(g_{n}+2f_{n})}{h _{n}a_{0}+f_{n}}}{\frac{(f_{n}+h_{n})a_{0}+(g_{n}+ f_{n})}{h_{n}a_{0}+f_{n}}}
=\frac{(f_{n}+2h_{n})a_{0}+(g_{n}+2f_{n})}{(f_{n}+ h_{n})a_{0}+(g_{n}+f_{n})}
$
.

But, we also have that

$a_{n+1}=\frac{f_{n+1}a_{0}+g_{n+1}}{h_{n+1}a_{0}+f _{n+1}}$.

Setting

$\frac{f_{n+1}a_{0}+g_{n+1}}{h_{n+1}a_{0}+f_{n+1}}= \frac{(f_{n}+2h_{n})a_{0}+(g_{n}+2f_{n})}{(f_{n}+h _{n})a_{0}+(g_{n}+f_{n})}$

shows us that it must be the case that the following equations hold:

$f_{n+1}=f_{n}+2h_{n}$
$g_{n+1}=g_{n}+2f_{n}$
$h_{n+1}=f_{n}+h_{n}$
$f_{n+1}=g_{n}+f_{n}$.

Two of these must be redundant (if the system is consistent, that is).

We also have the initial conditions:
$f_{0}=1$
$g_{0}=2$
$h_{0}=1$.

At this point, I must admit, I handed off the solution to Mathematica (using the RSolve command). I got the following:

$f_{n}=\frac{1}{2}\left((1-\sqrt{2})^{n+1}+(1+\sqrt{2})^{n+1}\right)$,
$g_{n}=\frac{-(1-\sqrt{2})^{n+1}+(1+\sqrt{2})^{n+1}}{\sqrt{2}}$, and
$h_{n}=\frac{-(1-\sqrt{2})^{n+1}+(1+\sqrt{2})^{n+1}}{2\sqrt{2}}$.

The presence of all those $\sqrt{2}$'s is encouraging, to say the least. If you plug in these values of the coefficients, you obtain the following rather nasty expression:

$a_{n+1}=\frac{2\,{\left( 1 - {\sqrt{2}} \right) }^n\,
\left( -2 + {\sqrt{2}} + \left( -1 + {\sqrt{2}} \right) \,{a_0} \right) -
2\,{\left( 1 + {\sqrt{2}} \right) }^n\,
\left( 2 + {a_0} + {\sqrt{2}}\,\left( 1 + {a_0} \right) \right) }{
{\left( 1 - {\sqrt{2}} \right) }^n\,
\left( -2\,\left( 1 + {a_0} \right) + {\sqrt{2}}\,\left( 2 + {a_0} \right) \right)
- {\left( 1 + {\sqrt{2}} \right) }^n\,
\left( 2\,\left( 1 + {a_0} \right) + {\sqrt{2}}\,\left( 2 + {a_0} \right) \right)
}$
.

If you want to take the limit of this as $n\to\infty$, I would notice that essentially you have the following limit:

$\lim_{n\to\infty}\frac{C_{1}(1-\sqrt{2})^{n}+C_{2}(1+\sqrt{2})^{n}}{C_{3}(1-\sqrt{2})^{n}+C_{4}(1+\sqrt{2})^{n}}$,

where

$C_{1}=2(-2+\sqrt{2}+(-1+\sqrt{2})a_{0})$,
$C_{2}=-2(2+a_{0}+\sqrt{2}(1+a_{0}))$,
$C_{3}=(-2(1+a_{0})+\sqrt{2}(2+a_{0}))$,
$C_{4}=-(2(1+a_{0})+\sqrt{2}(2+a_{0}))$.

This may seem like an awful lot of work, but I think that you're almost there. I've probably posted more than I should. Can you finish?
• Jun 21st 2010, 06:50 AM
Ackbeet
Those numbers not in the domain of the iteration scheme are the following:

$x=-\frac{f_{n}}{h_{n}}=
-\left( \frac{{\sqrt{2}}\,\left( {\left( 1 - {\sqrt{2}} \right) }^{1 + n} + {\left( 1 + {\sqrt{2}} \right) }^{1 + n} \right) }
{-{\left( 1 - {\sqrt{2}} \right) }^{1 + n} + {\left( 1 + {\sqrt{2}} \right) }^{1 + n}} \right)$
, for all $n\ge 0$.
• Jun 21st 2010, 07:07 AM
bolton_boy
I have just been to see my lecturer and he said the only clue he can give is that I should be able to just use this :

1.16 PROPOSITION. Suppose that (an) is an increasing sequence. Then:
(i) if (an) is bounded above, then it converges to its supremum;
(ii) if (an) is not bounded above, then it tends to infinity.
Similar statements apply to decreasing sequences.
• Jun 21st 2010, 07:10 AM
bolton_boy
I can see where you are coming from with your working out but I think its a bit too complex, from what I can tell it should be a fairly simple answer
• Jun 21st 2010, 07:13 AM
Ackbeet
I must disagree with your lecturer, then. The proposition he quoted simply does not apply to your sequence, because your sequence is not increasing or decreasing, no matter what initial point you choose. Here's an example:

Choose some initial value less than $\sqrt{2}$, say, $1$.

So,

$a_{0}=1$,
$a_{1}=1.5$,
$a_{2}=1.4$,
$a_{3}=1.41\overline{6}$,
etc.

The actual value of $\sqrt{2}=1.41421356237...$

Hence, you can see that the sequence oscillates about the limit, and is NOT increasing or decreasing.

The same thing happens if you were to choose a value larger than the limit.

In order to use the theorem your lecturer mentioned, your sequence MUST be monotone. Since yours is not, the theorem does not apply.
• Jun 21st 2010, 07:19 AM
Ackbeet
The theorem does not apply to the sequence as is. However, if you take the subsequence consisting of every other value, and show that it is monotone, you might be able to get somewhere with that theorem.

If I skip every other term, then I essentially have an iteration scheme as follows:

$a_{n+1}=\frac{3a_{n}+4}{2a_{n}+3}$.

If you can show that that one is monotone (either increasing or decreasing), then you're in business. So maybe you could show that the evens are increasing (for the numerical example I gave above) and the odds are decreasing (where even and odd apply to the number $n$).

But you're still going to have to show that it converges to $\sqrt{2}$. You'd have to show that $\sqrt{2}$ is the supremum of the increasing subsequence, and the infimum of the decreasing subsequence, in order to make it work.
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last