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\left[\frac{n-2^{\left\lfloor\log_{2}n\right\rfloor}}{2^{\left% \lfloor\log_{2}n\right\rfloor}},\frac{n-2^{\left\lfloor\log_{2}n\right\rfloor}% +1}{2^{\left\lfloor\log_{2}n\right\rfloor}}\right]\subseteq\left[0,1\right]$.

Proof.

$\displaystyle n-2^{\left\lfloor\log_{2}n\right\rfloor}\geq 0$ and $\displaystyle n-2^{\left\lfloor\log_{2}n\right\rfloor}+1\leq 2^{\left\lfloor% \log_{2}n\right\rfloor}$. This in turn is equivalent to showing that, for every positive integer $n$, $\displaystyle 2^{\left\lfloor\log_{2}n\right\rfloor}\leq n$ and $\displaystyle n+1\leq 2^{\left\lfloor\log_{2}n\right\rfloor+1}$.

The first inequality  is easy to prove: For every positive integer $n$, $\displaystyle 2^{\left\lfloor\log_{2}n\right\rfloor}\leq 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}\leq n\leq 2^{k}-1$. Then $\displaystyle n+1\leq 2^{k}=2^{k-1+1}=2^{\left\lfloor k-1\right\rfloor+1}=2^{% \left\lfloor\log_{2}2^{k-1}\right\rfloor+1}\leq 2^{\left\lfloor\log_{2}n\right% \rfloor+1}$. ∎

Title regarding the sets $A_{n}$ from the traveling hump sequence RegardingTheSetsAnFromTheTravelingHumpSequence 2013-03-22 16:14:28 2013-03-22 16:14:28 Wkbj79 (1863) Wkbj79 (1863) 6 Wkbj79 (1863) Proof msc 28A20