Finding lim sup and lim inf of a recursive sequence

Question

I have to find the $\lim \sup_{k \rightarrow \infty } a_k$ and $\lim \inf_{k\rightarrow \infty} a_k$ for the sequence with $(a_n)_{n \in \mathbb{N}}$: $$a_1 = 0, \\ a_{2m} = \frac{a_{2m-1}}{2}, \\ a_{2m+1} = \frac{1}{2}+ a_{2m}\\$$

I don't really know how to solve it. Do I have to find out the limit of $a_{2m}$ first? $$\lim_{a\to\infty}\frac{a_{2m-1}}{2}$$ Or do I have to plug in the second equation into the third and then calculate the limit? Thank you for your help.

Answer 1

Notice that: $$a_{2m} = \frac {a_{2m-1}} 2 = \frac {\frac 1 2 + a_{2m - 2}} 2 = \frac 1 4 + \frac 1 2 a_{2m-2}$$ $$a_{2m+1} = \frac 1 2 + a_{2m} = \frac 1 2 + \frac {a_{2m-1}} 2 = \frac 1 2 + \frac 1 2 a_{2m - 1}$$ So if we let $b_m = a_{2m}$ and $c_m = a_{2m+1}$, then $$b_m = \frac 1 4 + \frac 1 2 b_{m-1}$$ $$c_m = \frac 1 2 + \frac 1 2 c_{m-1}$$

There are at least two methods to compute $\lim_{m \to \infty} b_m$ and $\lim_{m \to \infty} c_m$. Let us consider the sequence $(b_m)_{m \in \mathbb N}$ for example. It is useful to look at the first few terms: $$0 \qquad \frac 1 4 \qquad \frac 3 8 \qquad \frac 7 {16} \qquad \frac {15} {32} \qquad \dotsb$$

Method 1

First we prove that the sequence is convergent. In order to do this it is enough to prove that it is bounded and monotonic.

By plotting the first few terms on the real line we conjecture that the sequence is bounded by $\frac 1 2$ and that it is increasing. We can prove the first claim by induction on $m$:

• $0 < \frac 1 2$ is clear.
• Suppose $m > 0$ is such that $b_{m-1} < \frac 1 2$. Then $b_m = \frac 1 4 + \frac 1 2 b_{m-1} < \frac 1 4 + \frac 1 2 \cdot \frac 1 2 = \frac 1 2$.

For the second claim, the inequality $b_m > b_{m-1}$ amounts to $\frac 1 4 + \frac 1 2 b_{m-1} > b_{m-1}$, which reduces to $b_{m-1} < \frac 1 2$, which we have already shown to be true.

Now that we know that $(b_m)_{m \in \mathbb N}$ is convergent, let $b = \lim_{m \to \infty} b_m$. Since $\lim_{m \to \infty} b_{m-1} = b$ as well, we have $$b = \frac 1 4 + \frac 1 2 b \qquad\implies\qquad b = \frac 1 2$$ therefore $\lim_{m \to \infty} b_m = \frac 1 2$.

Method 2

By looking at the first few terms of the sequence, we might conjecture that $$b_m = \frac 1 2 - \left ( \frac 1 2 \right )^{m+1}.$$

Let us prove the claim by induction on $m$:

• $b_0 = \frac 1 2 - \frac 1 2 = 0$ is true.
• Suppose $m > 0$ and $b_{m-1} = \frac 1 2 - \left ( \frac 1 2 \right )^m$. Then $$b_m = \frac 1 4 + \frac 1 2 \left [\frac 1 2 - \left ( \frac 1 2 \right )^m \right] = \frac 1 4 + \frac 1 4 - \frac 1 2 \cdot \left ( \frac 1 2 \right )^m = \frac 1 2 - \left ( \frac 1 2 \right )^{m+1}$$ so we are done.

Now it is easy to compute the limit: $$\lim_{m \to \infty} b_m = \lim_{m \to \infty} \left [\frac 1 2 - \left ( \frac 1 2 \right )^{m+1} \right ] = \frac 1 2.$$

With a similar reasoning you can prove that $\lim_{m \to \infty} c_m = 1$. Now you should be able to compute $\limsup_{m \to \infty} a_m$ and $\liminf_{m \to \infty} a_m$ from what we have shown.