$\limsup_n \left[\frac{q_n}{2^{p_n}};\frac{q_n+1}{2^{p_n}}\right[=[0;1[?$

Question

Let $X=[0;1[.$ Prove that for every $n \in \mathbb{N}^*$ there exist a unique decomposition : $n=2^{p_n}+q_n$ where $p_n \in \mathbb{N}$ and $0 \leq q_n <2^{p_n}.$

Considering $p_n$ and $q_n$ defined before, let $X_n=[\frac{q_n}{2^{p_n}};\frac{q_n+1}{2^{p_n}}[.$ Find $\limsup_nX_n$ and $\liminf_nX_n.$

Concerning the first part, there exist unique $p_n:=\left\lfloor{\ln(n)/\ln(2)}\right\rfloor$ and $q_n:=n-2^{p_n}.$

So $\liminf_nX_n=\emptyset$ ($X_{k}$ and $X_{k+1}$ are disjoint).

It remains to find $\limsup_nX_n,$ it seems to be equal to $[0;1[.$

Any way how to find it?

Answer 1

Your comment is an interesting idea, but I was thinking of something simpler -

Lemma: If $m$ is any power of two, and $i \in \{ 0, \dots, m-1\},$ then $$ X_{m+i} = [i/m, (i+1)/m).$$

Proof: $m+i = 2^{\log_2 m} + i,$ and $\log_2 m$ is an integer because $m$ is a power of two. Further, note that by assumption, $ 0\le i < m$. Thus, $2^{p_{m+i}} = m$ and $q_{m + i} = i$. QED.

As a simple corollary, we find that for any $m$ that is a power of two, $\bigcup_{i = 0}^{m-1} X_i = [0,1).$

Now, for any $n$, there exists a power of two larger than it - call this $m(n) = 2^{\lceil \log_2 n \rceil}$. Then $$ \bigcup_{k \ge n} X_k \supset \bigcup_{k = m(n)}^{2m(n) - 1} X_k = [0,1),$$ and so $\limsup X_n \supset [0,1)$. Of course, since $0 \le q_n < 2^{p_n}$ for every $n$, each $X_k$ is a subset of $[0,1)$, and so it follows that $\limsup X_k = [0,1)$.