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

share|cite|improve this question
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
up vote 4 down vote accepted

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

share|cite|improve this answer

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

share|cite|improve this answer

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

share|cite|improve this answer
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: – 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

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.