<s>[INST] Finding $\lim \sup, \lim \inf$ for sequence $s_n$ defined by $s_1=0$, $s_{2m}=\frac{s_{2m-1}}{2}$ $s_{2m+1}=\frac{1}{2}+s_{2m}$ I want to find $\lim \sup, \lim \inf$ for the sequence $s_n$ defined by $s_1=0$, $s_{2m}=\frac{s_{2m-1}}{2}$ $s_{2m+1}=\frac{1}{2}+s_{2m}$. So $s_n$ depends on $s_{n-1}$, but the dependence is dependant on even and odd n. 
The strategy given is to write down the 10 or so terms to figure out a conjecture about $s_n$, then use induction to prove said conjecture and then solve the problem. I really don't know where to start on this problem. Here's how I wrote out the sequence:

$s_1 = 0, s_2 = 0, s_{2(1)+1} = \frac{1}{2}, s_4=1, s_5= \frac{3}{4}, s_6= \frac{3}{8}, s_7 = \frac{7}{8}, s_8= \frac{7}{16}, s_9 = \frac{15}{16}, s_{10}= \frac{15}{32} $

I don't know what I'm supposed to make of this. I have a feeling the sequence is 'bouncing' between $\frac{1}{2}$ and 1 so I'm guessing those would be my lip sup and lim inf, but how do I prove this? 
 [/INST] You just have to note the following pattern in your sequence.
$$
s_n = \begin{cases}
1- \dfrac 1{2^{\frac{n-1}{2} }} & n \neq 1 \text{ odd} \\
\dfrac 12 - \dfrac 1{2^{\frac{n}{2} }} & n \text{ even} 
\end{cases}
$$
To see this, the base cases are easy to see: Put $n = 3$ and $s_3 = \frac{1}{2} = 1 - \frac 1{2^1}$, and $n=4$ gives $s_4 =\frac 14$ which is also $\frac{1}{2} - \frac{1}{2^2}$.
Induction: Assume that the above is true for even numbers up till $2k$, then we have to prove it is true for $2(k+1) = 2k+2$. Note that 
\begin{split}
s_{2k+2} & =  \frac{s_{2k+1}}2 \\
& = \frac{\frac{1}{2} + s_{2k}}{2}\\
& = \frac{\frac{1}{2} + \frac{1}{2}- \frac{1}{2^k}}{2} \\ & = \frac{1 - \frac{1}{2^k}}{2} \\ & = \frac{1}{2} - \frac{1}{2^{k+1}} 
\end{split}
Which was to be proved.
Now, assume it is true for odd numbers up till $2k-1$, then want to show it is true for $2k+1$.Note that:
\begin{split}
s_{2k+1} & =  \frac{1}{2} + s_{2k} \\
& = \frac{1}{2} + \frac{s_{2k-1}}{2}\\
& = \frac{1 + \left(1 - \frac 1{2^{k-1}}\right)}{2} \\ & = \frac{2 - \frac 1{2^{k-1}}}{2}\\ & = 1 - \frac{1}{2^k} \\ & = 1-\frac{1}{2^\frac{(2k+1)-1}{2}} 
\end{split}
Which was to be proved. Hence the induction is complete, and the result stands.
Now, note that $s_n-s_m$ is of the following forms:
If $n$,  $m$ are both odd, then it is $-\frac 1{2^{\frac{n-1}{2} }} + \frac 1{2^{\frac{m-1}{2} }} $, which converges to zero as $n,m$ increase.
If $n$,  $m$ are both even, then it is $-\frac 1{2^{\frac{n}{2} }} + \frac 1{2^{\frac{m}{2} }} $, which converges to zero as $n,m$ increase.
However, if $n$ is odd, $m$ is even, then it is $\frac 12-\frac 1{2^{\frac{n-1}{2} }} + \frac 1{2^{\frac{m}{2} }} $, which converges to half as $n,m$ increase.
Similarly, if $n$ is even, $m$ is odd, then it is $-\frac 12-\frac 1{2^{\frac{n}{2} }} + \frac 1{2^{\frac{m-1}{2} }} $, which converges to negative half as $n,m$ increase.
Now, any convergent sequence must be Cauchy. Hence, this difference must go to zero as $n,m$ increase. However, in the third and fourth case, we can clearly see that the difference doesn't go to zero. 
Hence, in every convergent subsequence of $s_n$ ,$n$  must eventually have the same sign.
Now, one sign leads to $\frac 12$, the other sign leads to $1$. Hence, these are the only two limits of the sequences $s_n$. Now it is clear that $\liminf s_n =  \frac 12$, $\limsup s_n = 1$.
</s>