I would like to know how to prove that :
$ \dfrac{x}{2}< 2^{\lfloor\log_2 (x) \rfloor} \leq x$
for $x \in \mathbb{N}_+ $
Should I proceed by induction? By contradiction?
Thank you
inequality \frac{x}{2}< 2^{\lfloor\log_2 (x) \rfloor} \leq x
-
0Yes, I mean log base$2$:) I don't really see how to prove that... – 2012-10-08
3 Answers
We know that, for any real number $a$, $a - 1 < \lfloor a\rfloor \leq a.$ Therefore, for any positive $x$, we have $(\log_2 x) -1<\lfloor \log_2 x\rfloor \leq \log_2 x.$ Raising $2$ to each of these expressions, we obtain $2^{(\log_2 x) - 1}<2^{\lfloor \log_2 x\rfloor}\leq 2^{\log_2 x}\text{, or}$ $ \frac x 2 < 2^{\lfloor \log_2 x\rfloor}\leq x.$
I suspect what your professor expects you to do is expand that middle term:
$ 2^{log(x)} = x ^{log(2)}$
Then you just have to show that
$ \frac{x}{2} < x^{log(2)} \leq x $
The easiest way to get that done is to actually show it's true for a base case (like x = 1), then show that, for $ x \geq 1 $, the inequality for x implies the inequality for x +1 (i.e. proceed by induction).
Actually, it may be easier to show that it's true for x = 1 and x = 2, and then proceed by induction assuming $ x \geq 2 $.
-
0This is ignoring the floor stuff compleetly, isn't it? – 2012-10-18
Here by $\log$ we mean logarithm to the base $2$.
If we are allowed to use basic properties of logarithms, the problem is straightforward. Let $a=\lfloor \log x\rfloor$. Then $\log x=a+e$, where $0\le e\lt 1$.
The inequality on the right is obvious. For the inequality on the left, note that $x=2^{\log x}=2^a2^e.$ But $2^e\lt 2$. It follows that $2^a\gt \frac{1}{2}x$. If we do not wish to use the word "obvious" for the inequality on the right, use $1\le 2^e\lt 2$.