# An induction problem.

I am trying to prove the following problem by induction on $n$.

Let $T: (0,1]\rightarrow (0,1]$ be given by $T(x)=\left\{ \begin{array}{ll} 2x & \quad \text{if} \hspace{4mm} 0<x \leq \frac{1}{2} \\ 2x-1 & \quad \text{if} \hspace{4mm} \frac{1}{2}< x \leq 1. \end{array} \right.$

Define a function $d_1$ by $d_1(x)=\left\{ \begin{array}{ll} 0 & \quad \text{if} \hspace{4mm} 0<x \leq \frac{1}{2} \\ 1 & \quad \text{if} \hspace{4mm} \frac{1}{2}< x \leq 1. \end{array} \right.$

and let $d_i(x)=d_1(T^{i-1}(x))$. Then for all $x\in (0,1]$ and $n\geq 1$, $$\displaystyle \sum_{i=1}^n \frac{d_i(x)}{2^i}<x\leq \sum_{i=1}^n \frac{d_i(x)}{2^i} +\frac{1}{2^n}.$$

The base case is easy. I am having trouble using the inductive hypothesis, though (I'm assuming that the inequality holds for some $n$. I'm trying to split up the sums like this

$$\displaystyle \sum_{i=1}^{n}\frac{d_i(x)}{2^i}+\frac{d_{n+1}(x)}{2^{n+1}}<x\leq\sum_{i=1}^{n}\frac{d_i(x)}{2^i}+\frac{d_{n+1}(x)}{2^{n+1}}+\frac{1}{2^{n+1}},$$

but I still don't see how to finish. Could someone help me out? Thank you.

-
Can you prove that it is true for $n=2$? I believe that is all that you really require. –  Calvin Lin Sep 25 '13 at 5:42
I've tried this for the case when $n=2$. I just don't know how to show that the inequality is true in general. Also, I don't know why we don't have equality on the LHS. –  Tim Sep 25 '13 at 5:45
Ah, I get a nice interpretation of the formula by looking at base 2 notation. However, the definition of $d(x)$ is throwing it off slightly. The basic idea is that the terms are the base 2 expansion, cut off at the $i$th term. It doesn't work too nicely, as $0.5 = (0.10000\ldots)_2$ has $d_1 = 0$ but I would like for it to be 1.... –  Calvin Lin Sep 25 '13 at 5:55

Let the base 2 expression of $x$ be $( 0. x_1 x_2 x_3 \ldots )_2$.

Hint: Show that $d_i (x) = x_i$, except when all of the remaining terms are 0. In this case, $d_i(x) = 0$.

Hence, the result follows.

This technically doesn't use induction.

-

Suppose that the non-terminating binary expansion of $x$ is

$$x=\sum_{k\ge 1}\frac{a_k}{2^k}\;;$$

show by induction on $n$ that

$$T^n(x)=\sum_{k\ge 1}\frac{a_{k+n}}{2^k}\;.$$

In other words, if $x=0.a_1a_2a_3\ldots$ in binary, where infinitely many of the $a_k$ are $1$, then $T^n(x)=0.a_{n+1}a_{n+2}a_{n+3}\ldots\;$.

Then show that $d_1(x)=a_1$, and the result follows quite easily.

-