Sarah Sarah

Posted on Thursday, 20 November, 2003 - 08:20 pm:

Please help me show that the sequence
s_n+1 =(5s_n -3)/(s_n +1)
tends to 3 where 1/3 < s₁ < 1
(I have managed to do this for all other values of s₁ )
thanks
Sarah

Graeme McRae

Posted on Thursday, 20 November, 2003 - 09:46 pm:

If s₂ is between 1/3 and 1, then the series converges to 3, because in that case, s₁ > 5, and you've already shown it converges when s₁ is not between 1/3 and 1.

If the series converges when s₂ is between 1/3 and 1, then the series converges when s₁ is in that range.

--Graeme

Andre Rzym

Posted on Friday, 21 November, 2003 - 07:49 am:

Graeme, maybe I'm missing something, but if, for example, S₂ =1/2, then S₁ = 7/9 (which is not greater than 5).

I would start the whole problem by sketching the function (plot S_n+1 vs S_n )

Then look for 'fixed points' -values of S_n for which S_n+1 = S_n . There are two (1 and 3).

Then look at when the formula blows up -i.e. when S₁ =-1. But S₁ =1/3 is similarly a problem since S₂ =-1. Ditto S₁ =5/7 etc.

Having dealt with the special cases, now come up with a conjecture as to how convergence actually works. I haven't looked at this carefully, but something like the following might work:

1) If 3 < S_n then 3 < S_n+1 < S_n
2) If S_n < -1 then S_n+1 > 3. So if you can prove convergence for (1) you have it for (2) also.
3) If -1 < S_n < 1 then S_n+1 < S_n < 1, and after enough iterates, S < -1 which takes you to (2) [provided, of course we do not hit -1]
4) If 1 < S_n < 3 then 1 < S_n < S_n+1 < 3

Andre

Sarah Sarah

Posted on Friday, 21 November, 2003 - 08:56 am:

Andre,

I have all ready done all that; my problem is showing that after enough iterates S < -1 in case (3) (this is fairly obvious on the graph but I'm looking for a nice non-graphical method). I was going to try finding bounds on (1-s_n+1 )/(1-s_n ) or something..

Cheers
Sarah

Sarah Sarah

Posted on Friday, 21 November, 2003 - 11:08 am:

Oh,
Does it suffice to say that in case (3) s_n is decreasing and can't tend to a lower limit since x=(5x-3)/(x+1) has no solutions less than 1?
Sarah

Andre Rzym

Posted on Friday, 21 November, 2003 - 01:36 pm:

I don't think your argument is strong enough. One could conceive of a monotonically decreasing series tending to some value, but where the value was not a solution of the original equation.

What you are trying to show is, for a given $S_{n}$ ( $< 1$ ), that after a finite number of iterations of the function you can guarantee that you will be outside the $(- 1, 1)$ range.

Try writing $S_{n} = 1 - δ$ .

$S_{n + 1} = (5 - 5 δ - 3) / (2 - δ) = (2 - 5 δ) / (2 - δ)$

If numerator and denominator are positive, $S_{n + 1}$ is less than $(2 - 5 δ) / 2 = 1 - 5 δ / 2$ .

Note that this is decreasing linearly with $δ$ . So you can come up with an upper bound of $n$ before which $S_{n} < 0$ .

The above is more a guide than a proof. Can you finish it off from here? If not, I'll post a complete proof.

Andre

Sarah Sarah

Posted on Friday, 21 November, 2003 - 03:08 pm:

Yes the assumption that if a sequence defined by

s_{n + 1} = f (s_{n})

tends to a limit then that limit must satisfy

s = f (s)

was bothering me. Can you give me a proof or a counterexample?

Erm are you sure that

$(2 - 5 δ) / 2 > (2 - 5 δ) / (2 - δ)$ ?

I am stuck also here:

$s_{n} = (s_{n - 1}^{2} + s_{n - 2} + 2)^{1 / 3}$

$s_{1} = 1$ , $s_{2} = 3 / 2$

Prove that $s_{n}$ tends to 2.
I've shown the sequence is bounded and that if we assume the thing above the only possible limit is 2 - but I am having trouble showing it is monotonic.

Thanks again

Sarah

Anand Deopurkar

Posted on Friday, 21 November, 2003 - 03:09 pm:

I think it should be given that the formula does not blow up.
Then I have a different strategy.
Please bear with me because i dont know how to enter subscripts so i will write s(n)

If s(n) is 1 for any n then the limit is clearly 1 because 1 is a fixed point.
Let's assume s(n) is not 1 for any n.

S(n+1)=(5*S(n)-3)/(S(n)+1)
S(n+1)-1 = (4*S(n)-4)/(S(n)-1+2) Now put
T(n)=S(n)-1 then t(n) is not 0 for any n
T(n+1)=4*T(n)/(T(n)+2)
Now invert ie put x(n)=1/T(n)
x(n+1)=1/4 + x(n)/2
This is a very simple relation and there is no problem in finding its limit.

Andre Rzym

Posted on Friday, 21 November, 2003 - 04:11 pm:

I had in mind a function that was simply undefined at the limit. Eg

f(x) = x² .x^x

with a starting point of 0.5. This sort of behaviour is obviously not present in your function, but I would be reluctant to use the argument because I'm not certain on exactly what assumptions we are basing the argument. I stand open to correction here.

Finally, Anands's solution is very neat.

Andre

Anand Deopurkar

Posted on Friday, 21 November, 2003 - 04:29 pm:

If S(n+1)= f (S(n)) and if S(n) converges to S and if f is continuous at S then we can indeed say that S=f(S)
To prove this,
let T(n)=S(n+1) then T(n) has the same limit S
T(n)=f(S(n))
Then Lim T(n) = Lim f(S(n))
Now S(n) is a sequence converging to S and f is continuous at S hence Lim f(S(n)) = f(S)
and Lim T(n) = S therefore S=f(S)
Both the conditions that S converges and f is continuous at S are necessary.
Thus in your case if we could prove that the sequene converges, we can conclude that limit is 1 or 3.

Posted on Friday, 21 November, 2003 - 04:33 pm:

It is certainly true that if s_n+1 = f(s_n ), s_n -> s and f is defined in some neighbourhood of s, and is continuous at s, then f(s) = s.

Proof: since s_n -> s we have f(s_n ) -> f(s) as f is continuous at s. Also s_n+1 -> s. Hence taking the limit of the equation s_n+1 = f(s_n ) gives s = f(s).

In this case, the function is undefined at -1, but it's easy to treat that seperately. Alternatively, to show that s = f(s), you can just note that s_n+1 (s_n +1) = 5s_n -3 (*). So if s_n -> s then s_n+1 -> s so taking the limit of (*) we get s(s+1) = 5s-3.

Of course none of this actually proves the limit exists - to do that you could use the methods given in Andre or Anand's earlier posts.

Saul Foresta

Posted on Friday, 21 November, 2003 - 05:03 pm:

For showing s_n is monotonic, induction will work.

Graeme McRae

Posted on Saturday, 22 November, 2003 - 07:34 pm:

Andre, no you didn't miss anything; I misread the function in the first place, and mistakenly thought this problem was a lot easier than it is.

The function is monotonic if s₁ is greater than 1, which, as Saul points out can be shown by induction.

But if s₁ < 1, the function bounces around a bit until s_n is greater than 1, at which time it becomes monotonic.

If you plot a graph of y=(5x-3)/(x+1), and on the same paper, plot y=x, you can demonstrate to yourself the behavior of s_n . Start at any point on y=(5x-3)/(x+1), and draw a line horizontally to the graph of y=x, then draw a line vertically to the graph of y=(5x-3)/(x+1). This sawtooth represents one iteration of s_n .

Clearly, if you start anywhere greater than x=1, the sawteeth (is that a word?) get smaller and smaller, but keep going in the same direction, toward three.

But if you start anywhere less than 1, then you get sawteeth that get bigger and bigger until they turn into a big spiral that circles around the origin, and ends up in the upper right quadrant somewhere.

Once again, it's possible that I've somehow missed an important point, so I apologize in advance if this post is off-target! (sheepish grin)

--Graeme