Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$, \begin{equation} \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}. \end{equation}

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.

share|cite|improve this question
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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.