How do I show a sequence like this is bounded?

[bbb999]

I have a sequence where s_1 can take any value and then s_{n+1}=\frac{s_n+10}{s_n+1}

How do I show a sequence like this is bounded?

 

[Gerenuk]

I guess you can try thinking if
http://en.wikipedia.org/wiki/Cobweb_diagram
helps. Maybe this already shows that it is bound!

Or with a transformation x_t=y_{t+1}/y_t+a you can easily solve this recursion relation explicitely. Let me know if you need the details.

 

[bbb999]

Well I know the limits of s_{n+1} and s_n are the same. Solving for the limit fives the limit to be \pm \sqrt{10} so does that not mean the upper and lower bounds are these?

 

[Mark44]

The sequence clearly converges to 1, so an upper bound for at least the tail of the sequence (all but a finite number of terms at the beginning of the sequence) would be any number larger than 1 (say 2), and a lower bound for the tail would be any number smaller than 1 (say 0).

 

[Mark44]

Well I know the limits of s_{n+1} and s_n are the same. Solving for the limit fives the limit to be \pm \sqrt{10} so does that not mean the upper and lower bounds are these?

The limit of the sequence is 1. How did you get +/-sqrt(10)?

Recursive sequences usually give a starting value, which you didn't include. If I assume that s₀ = 0, then s₁ = 10 > sqrt(10), so sqrt(10) is not an upper bound for the sequence.

 

[statdad]

The sequence clearly converges to 1, so an upper bound for at least the tail of the sequence (all but a finite number of terms at the beginning of the sequence) would be any number larger than 1 (say 2), and a lower bound for the tail would be any number smaller than 1 (say 0).

I'm not sure why you say this ("The sequence clearly converges to 1"): assume for a second that it does converge, then use the relation to find the value of the limit. I don't get one, and my explorations (wxmaxima, sage) don't indicate that either.

 

[bbb999]

The sequence converges to \sqrt{10} for any initial value chosen other than -\sqrt{10}

 

[Mark44]

I might not be thinking about this the right way...

 

[bbb999]

I used scilab to work out the iterations of the sequence and my above post is correct I think?

 

[statdad]

@bbb999 - yes.

 

[bbb999]

@statdad

Sorry is that yes for the original posts about upper and lower bounds being \pm \sqrt{10}?

 

[Tedjn]

Your claim about convergence might be right; I haven't thought it through so I can't confirm or deny. If true, you can use convergence to prove that the sequence is bounded, but the two are not the same. Why and how? Also, you need to assume that your starting value of s₁ never causes a divide by zero in the middle.

 

[Office_Shredder]

The sequence converging to \pm \sqrt{10} is correct, assuming it converges. Unfortunately this doesn't give any sort of proof, because you assumed convergence in finding the value that it would converge to (and these do not give bounds for the sequence)

It might help to start by asking a question: What has to happen for s_n > 10? (thinking about s_n-1) How often can this occur?

 

[Mark44]

My ignorance of recursive sequences, especially nonlinear ones, shows in this thread. Can someone how you find bounds for the sequence in this thread? Only a few of my DE texts spend much time on recursive sequences, and none spends any time on nonlinear ones such as this. I wasn't able to find anything on bounds of recursive sequences on the Web, either.
Thanks,
Mark

 

[Mark44]

I think that if you assume the sequence converges, then you can assume s_n+1 is "close to" s_n, so you can write s_n = (s_n + 10)/(s_n + 1), from which you get (s_n)² = 10. This would put s between -sqrt(10 and +sqrt(10).

Doing some calculations using Excel, and choosing values of s₁, it appears that sqrt(10) is a stable fixed point of the sequence, with most of the starting values for s₁ converging to that value. The other fixed point, -sqrt(10), seems to be an unstable fixed point. The only value (of the relatively few I tried) that converged to -sqrt(10) was -sqrt(10).

Comments welcome.

 

[Tedjn]

I don't know the general theory behind this, but here is one quick way to reason about some bounds without reasoning about convergence. In this case, let f(x) = (x+10)/(x+1). For x > -1, it is always decreasing with lower bound 1. If s₀ > 1, I hope it is clear that f(1) is an upper bound. If -1 < s₀ ≤ 1, then f(s₀) is an upper bound. Similar reasoning probably exists for the other branch of the function. This doesn't really touch on convergence at all (although I would not be surprised if the convergence features you discuss can be proved with some more work).