regarding the sets $A_n$ from the traveling hump sequence

In this entry, $\lfloor \cdot \rfloor$ denotes the floor function.

Following is a proof that, for every positive integer $n$, $[{\displaystyle \frac{n-2^{\lfloor {\log }_{2}n\rfloor }}{2^{\lfloor {\log }_{2}n\rfloor }}},{\displaystyle \frac{n-2^{\lfloor {\log }_{2}n\rfloor }+1}{2^{\lfloor {\log }_{2}n\rfloor }}}]\subseteq [0,1]$.

Proof.

Note that this is equivalent (http://planetmath.org/Equivalent) to showing that, for every positive integer $n$,

$n-2^{\lfloor {\log }_{2}n\rfloor }\ge 0$ and $n-2^{\lfloor {\log }_{2}n\rfloor }+1\le 2^{\lfloor {\log }_{2}n\rfloor }$. This in turn is equivalent to showing that, for every positive integer $n$, $2^{\lfloor {\log }_{2}n\rfloor }\le n$ and $n+1\le 2^{\lfloor {\log }_{2}n\rfloor +1}$.

The first inequality is easy to prove: For every positive integer $n$, $2^{\lfloor {\log }_{2}n\rfloor }\le 2^{{\log }_{2}n}=n$.

Now for the second inequality. Let $n$ be a positive integer. Let $k$ be the unique positive integer such that

$2^{k-1}\le n\le 2^k-1$. Then $n+1\le 2^k=2^{k-1+1}=2^{\lfloor k-1\rfloor +1}=2^{\lfloor {\log }_2{2}^{k-1}\rfloor +1}\le 2^{\lfloor {\log }_{2}n\rfloor +1}$. ∎

Title	regarding the sets $A_n$ from the traveling hump sequence
Canonical name	RegardingTheSetsAnFromTheTravelingHumpSequence
Date of creation	2013-03-22 16:14:28
Last modified on	2013-03-22 16:14:28
Owner	Wkbj79 (1863)
Last modified by	Wkbj79 (1863)
Numerical id	6
Author	Wkbj79 (1863)
Entry type	Proof
Classification	msc 28A20