Proving Nested Intervals Converge to $\alpha$

[alexmahone]

Let $\alpha$ be a real number between 0 and 1 written in binary: e.g.,

$\alpha=.1011001\ldots$ means $\alpha=\frac{1}{2}+\frac{1}{2^3}+\frac{1}{2^4}$$+\frac{1}{2^7}+\ldots$

Make a set of nested intervals by starting with $I_0=[0,\ 1]$, then defining recursively $I_n$ to be the (closed) left half of $I_{n-1}$ if the $n$-th place of $\alpha$ is 0, and the (closed) right half if the $n$-th place is 1.

Prove that the resulting sequence of nested intervals converges to $\alpha$, i.e., $\alpha$ is the unique number inside all the intervals.

 

[alexmahone]

How do I prove that $\alpha$ is always between the two endpoints?

 

[nimon]

Hi there,

I'll call the $0.1011001\ldots$ bit the decimal expansion and the $\frac{1}{2} + \frac{1}{2^{3}} + \ldots$ the series expansion. Let's define $\alpha_{k}$ to be the $k^{\text{th}}$ term in the decimal expansion of $\alpha$.

After some thought I think I can show that

$I_{n} = \left[ \sum_{k=1}^{n} \frac{\alpha_{k}}{2^{k}} , \frac{1}{2^{n}} + \sum_{k=1}^{n} \frac{\alpha_{k}}{2^{k}} \right].$

All this says is: the left boundary of $I_{n}$ is formed by taking the first $n$ terms of the series expansion of $\alpha$, and the right boundary is $\frac{1}{2^{n}}$ bigger!

I will leave you to prove this yourself, for which I recommend induction on $n$. I'd first convince myself by writing out the first few cases by hand (unless your really bright and can see it straight away, took me a while).

Once you have this, it shouldn't be too hard to show that

$\alpha \in I_{\infty} = \lim\limits_{n\rightarrow\infty}\bigcap\limits_{k=0}^{n} I_{n}.$

Just showing that $\alpha\in I_{n}$ for arbitrary $n$ should do the trick.

On the other hand, what if $I_{\infty}$ contained some other element than $\alpha$? Could we get some contradiction?

---------- Post added at 08:21 PM ---------- Previous post was at 08:13 PM ----------

Actually, If you can prove that $I_{n}$ does indeed have the form I gave (which I haven't done yet, just going on my quick workings!), then since $\frac{1}{2^{n}}$ becomes zero and $\sum_{k=1}^{n} \frac{\alpha_{k}}{2^{k}}$ goes to $\alpha$ as $n$ goes to infinity, it should follow that $I_{\infty} = [\alpha,\alpha] = \alpha$.