Find the upper and lower limits of the sequence defined by From Principles of Mathematical Analysis, third edition. p79, problem 4. 

Find the upper and lower limits of the sequence $\{s_n\}$ defined by
$$s_1 = 0; s_{2m}=\frac{s_{2m-1}}{2}; s_{2m+1}= {1\over 2} + s_{2m}$$

The first thing I did was write out the first few terms in the sequence:
$$\{0,0,\frac{1}{2},\frac{1}{4},\frac{3}{4},\frac{3}{8},\frac{7}{8},\frac{7}{16}, \frac{15}{16}, \cdots \}$$
Intuitively it seems clear that the limits are 1 and 1/2. However, I do not know how to show this formally. I also plugged formulae together to get this:
$$s_{2m} = \frac{0.5 + s_{2m-2}}{2}; s_{2m+1} = \frac{s_{2m-1}+1}{2}$$
But I really don't know to use limits with this. My professor told me I need to use these formal definitions of the even and odd terms. How might I do this?
 A: You're on the right track. You've noticed that the even and odd parts of the sequence appear to converge differently. The first step is to come up with formula for the even and odd parts. We can then treat these as separate sequences and find their limits. We begin by noting that both sequences are Cauchy. We'll begin with the even sequence.
I propose that 
$$0.5>s_{2m}=\frac{0.5+s_{2m-2}}{2}$$
That is, after some simple algebra,
$$0.5>s_{2m-2}=\frac{0.5+s_{2m-4}}{2}$$
Some more algebra, and we see we have
$$0.5>s_{2m-4}$$
I'm sure you can see by now we can inductively do this until we hit $0.5>s_2=0$, which is clearly true. So, the sequence is bounded above, but how does that help? Well, now that we know this, we can observe that
$$s_{2m+2}-s_{2m}=\frac{0.5+s_{2m}}{2}-s_m=\frac{0.5-s_{2m}}{2}>0,$$
and so the sequence is actually increasing. Now, in the real numbers, an increasing sequence that is bounded above must converge, and any convergent real sequence is Cauchy. Thus, to find the actual limit, we can assume for large enough $m$ that $s_{2m}=s_{2m-2}$ and we have
$$s_{2m}=\frac{0.5+2_{2m-2}}{2}=\frac{0.5+s_{2m}}{2}$$
$$2s_{2m}=0.5+s_{2m}$$
$$s_{2m}=0.5$$
As we expected. For the odd sequence, we proceed in largely the same manner. I propose that $1>s_{2m+1}$. As above, this will lead to a large chain of simply decreasing the index:
$$1>s_{2m+1}=\frac{1+s_{2m-1}}{2}$$
$$1>s_{2m-1}.$$
and so on. So, the sequence is bounded by $1$ above. Now observe that
$$s_{2m+1}-s_{2m-1}=\frac{1+s_{2m-1}}{2}-s_{2m-1}=\frac{1-s_{2m-1}}{2}>0.$$
The sequence is increasing, great. Therefore it must converge, is Cauchy, and we can assume for large enough $m$ that $s_{2m+1}=s_{2m-1}$ giving
$$s_{2m+1}=\frac{1+2_{2m-1}}{2}=\frac{1-s_{2m+1}}{2}$$
$$2s_{2m+1}=1+s_{2m+1}$$
$$s_{2m+1}=1$$
As expected.
Wrapping it all together, we see that the even sequence is bounded by $0.5$ and converges to that bound, and the odd sequence is bounded by $1$ and converges to that bound. We can then conclude that the upper limit of the entire sequence is $1$ and the lower limit is $0.5$.
