inequality $\frac{x}{2}< 2^{\lfloor\log_2 (x) \rfloor} \leq x$

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

-
To get floor, you use \lfloor and \rfloor. So \lfloor \log(x) \rfloor gives $\lfloor \log(x) \rfloor$ – Ross Millikan Oct 8 '12 at 20:35
I assume by $\log$ you mean $\log_2$ (base $2$). Then you don't need induction if you are allowed to use basic properties of exponents, logarithms. – André Nicolas Oct 8 '12 at 20:38
Yes, I mean log base 2 :) I don't really see how to prove that... – eouti Oct 8 '12 at 20:39

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$.

-
Yes, I started with the base case, x=1, but I can't get it for x+1 – eouti Oct 8 '12 at 20:41
Then I suggest you use a second base case, $x = 2$. It should be easier to show that $\frac{x}{2} < x^{log(2)} \leq x \Rightarrow \frac{x+1}{2} < (x+1)^{log(2)} \leq x +1$ if you assume that $x \geq 2$ (which you can, by using a second base case). – Mathew Calkins Oct 8 '12 at 20:54
tomasz: I said exactly what I meant. The expression $2^{log x} = x^{log 2}$ is true for all real $x$. Feel free to check that on Wolfram Alpha, if you like: wolframalpha.com/input/?i=y+%3D+x%5E%28ln+2%29+-+2%5E%28ln+x%29 – Mathew Calkins Oct 8 '12 at 21:01
This is ignoring the floor stuff compleetly, isn't it? – Hagen von Eitzen Oct 18 '12 at 15:11

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$.

-