How Can the Limit of a Monotone and Bounded Sequence be Found Using Induction?

[semidevil]

so x(1) := 8, and x(n + 1) = 1/2(X(n)) + 2. show that it is bounded and monotone, and find the limit.

so I claim that it is decreasing, i.e, X(n)> x(n+1).

by induction:

n = 1 implies 8 > 6. this checks.
assume K is true, try K + 1. so need to show X(k+1) > x(K+2). we know that X(K+2) = 1/2(x(k+1)) + 2, in othe words, need to show 1/2X(k+1) + 2 < (x(K+1)). bring x(k+1) to other side, then 2 < x(K+1) - 1/2x(k+1).

simplify and get 4 <= x(k+1).

so now, I know that x(k+1) is less then or equal to 4. this shows that it is bounded by 4 right? I was trying to show that it was decreasing...but I showed this instead. Does this assume that it is decreasing? and how?

and the final question. how do I show that the limit is 4?'


and question 2:

x1 >1, and x(n+1):= 2 - 1/x(n). same thing. now since x 1 is not specifically a number, I dotn know how to approach it.

so if I just do soem computations: I know that x1 = something greater then 1, so if I want x2, that is := 2 - 1/(x1), and x3 := 2 - 1/(x2). I'm going to guess that this will haev a bound of 2. now, since x1 is greater then 1, and it has a bound of 2. upper or lower, my head hurts, so I"m going to take a break and tackle tihs tommorow...but...let me think about it.

 

[AKG]

Assume x(k + 1) > x(k), then:
0.5x(k) + 2 > x(k)
x(k) < 4

If x(k) < 4, then 0.5x(k - 1) + 2 < 4
x(k - 1) < 4

So, a number in the sequence can be less than 4 only if it is preceeded by a number less than 4, but since we start with a number greater than 4 (we start with 8), this will never happen. And we started by showing that a number can be greater than the one before it only if it is less than 4, so we've showed that this will never happen, so it's decreasing. The best thing to do would probably have been to use "<" instead of "<" to show that it is decreasing, and not just non-increasing. This shows that it is decreasing, and also shows that it is bounded. Now, to compute the limit:

x(1) = 8
x(2) = 0.5x(1) + 2
x(3) = 0.5(0.5x(1) + 2) + 2 = 0.25x(1) + 3
x(4) = 0.5(0.25x(1) + 3) + 2 = 0.125x(1) + 3.5
x(5) = 0.0625x(1) + 3.75
.
.
.
x(n) = 0.5^(n - 1)x(1) + (4 - 4*0.5^(n - 1)) = 4(1 - 0.5^(n - 1))

Clearly, as n approaches infinity, x(n) approaches 4.

 

[AKG]

Assume the second sequence is not always decreasing(we want to derive a contradiction), then:

2 - 1/x > x
(for some x in the sequence... it may have been better to write x(n) instead of x, but I'm sure you'll get it)

In the first sequence, we showed a number could be less than 4 only if it were preceeded by one that was less than 4. In this one we can show a similar thing in that a number can be less than or equal to 1 only if it is preceeded by a number less than or equal to 1, and since we start with a number greater than 1, this will never happen. So we know that sequence is bounded below by 1 (this also tells us that all the numbers are positive). Going back to the inequality above, and given that x is positive, we get:

2x - 1 > x²
x² - 2x + 1 < 0
(x - 1)² < 0

A square number cannot be less than zero, so if the above inequality is to hold, then x = 1, but I suggested above that a number is less than or equal to 1 only if it is preceeded by such a number, and this would never happen since the first element is greater than 1, so the inequality does not hold. This inequality was based on the assumption that the sequence was not always decreasing. This contradiction implies that it is always decreasing (monotone decreasing), and we've shown it to be bounded.

We know 1 is a lower bound, so the limit, which would be the greatest lower bound, must be greater than or equal to 1 (not less than). Suppose it is greater than one, so 1 + e is the limit. Choose d = e²/(1 - e). Since 1 + e is the greatest lower bound, there must be an element of the sequence, X(k), such that 1 + e < X(k) < 1 + e + d.

But then

X(k + 1) = 2 - 1/X(k) < 2 - 1/(1 + e + d)
X(k + 1)(1 + e + d) < 2 + 2e + 2d - 1 = 1 + 2e + 2d
X(k + 1)(1 - e² + e²) < (1 + 2e)(1 - e) + 2e²
X(k + 1) < 1 + e

Which is clearly a contradiction, so the greatest lower bound is 1.

EDIT: If you've done delta-epsilon proofs, you'll know that you don't decide what d will be off the bat, and have everything magically fall into place. You work backwards, find the appropriate delta, and then work forwards. Also, don't focus on how I did these problems. I had no set, standard way of approaching this, I just thought about what I thought was true (and thus what I needed to prove), assumed it was false, then looked at the implications of such an assumption, looking for contradictions.

I thought it would be decreasing, so I assumed that for some x, it didn't decrease. Surely, this would say something about that x, so what does it say about it? I isolated x and found that it would have to be 1. So I assumed it was, and noted the implications (that it would have to be preceeded by 1) and noticed how this would be impossible, so that proved the first part for me. Then, finding the limit: for the first problem (where the limit was 4) it was pretty simple. It's an obvious recursive pattern and I just wrote a few lines until I was convinced I could write the general form for the nth term. Note that I didn't bother to prove it, but I could have done so (inductively) very easily if I wanted to.

For the second one, it may not seem as obvious. But I had a hunch that the limit would be 1. One reason for this was when I was assuming that the sequence wasn't always decreasing, I found that this would only happen if x were 1, and that this was impossible, so I knew that 1 was a lower bound, and it seemed "special" so I guessed it was the limit. Also, if you look at the formula for x(n + 1) (whether you're looking at the first problem or the second), you'll notice a "fixed point" where x(n + 1) = x(n). The fixed point is a good guess for your limit.

So, how did I prove it, i.e. how did I find the appropriate delta? Well I knew the limit was not less than 1 (I had proved that) and I figured it was 1, so I wanted to prove that it was not greater than 1. Assume the opposite, i.e. that it is greater than 1, and let it be 1 + e, for some small e > 0. I started by choosing some number in the sequence 1 + e + d, and finding out what the conditions on d would have to be for 2 - 1/(1 + e + d) to be less than or equal to 1 + e. Note that if were to be equal to 1 + e, then the next number which would be 2 - 1/(1 + e) would definitely be less than 1 + e. I found these conditions for d by isolating d in the inequality

2 - 1/(1 + e + d) < 1 + e

Then, knowing that I couldn't be certain that 1 + e + d was in the sequence, I could know for sure that there would be some number between 1 + e and 1 + e + d (otherwise, 1 + e + d would be the greatest lower bound, contradicting the assumption that 1 + e was the greatest lower bound). I took this number, and as you can see above, showed that its successor would be less than 1 + e, resulting in the desired contradiction.

So most of this involves working backwards, and much of it relies on proof by contradiction. Assume what you don't want to prove, and find a case where this assumption leads to contradictions. Hopefully you will have figured a general approach to these types of problems and will be able to do more on your own in the future, and haven't just tried to memorize the steps involved in my solution.

Hopefully I've given you a way to think about these problems, and not just a recipe for how to do them.

 

[HallsofIvy]

x₁= 8, x_n+1= (1/2)x_n+ 2.

To show that the sequence is decreasing you need to show x_n+1= (1/2)x_n+ 2< x_n. That's the same (subtract (1/2)x_n from both sides) as 2< (1/2)x_n or 4< x_n. If you can prove that, then you will have both that x_n is decreasing and that it has a lower bound!

Prove 4< x_n by induction: If n= 1, then x₁= 8> 4.

Now assume that, for some N, x_N> 4.

x_N+1= (1/2)x_N+ 2> (1/2)(4)+ 2= 4 and you are done.

The sequence is decreasing and has lower bound 4 so converges to some number greater than or equal to 4.


To determine what the limit is, take the limit of both sides of the recursion equation:
lim(x_n+1)= lim( (1/2)x_n+ 2).

Since x_n+1 and x_n are the same sequence, there limits are the same: writing "x" as the limit, x= (1/2)x+ 2. Solve for x.