# How to prove the following inequality without expansion

$M^k \le 2^r < M^{k+1}$

where $M>1 , k>0$ for some $r$.

It simply tells you that there exists a $2^r$ between $M^k$ and $M^{k+1}$. for example:

if $M=3$, $k=1$ then $$M^k = 3, \quad M^{k+1} = 9$$ and there exists $4$ and $8$ in between $3$ and $9$. i.e., $2^2$ and $2^3$

Edit: (T.B.)

Let $M \geq 2$ and $k \geq 1$ be integers. How can I prove that there exists an integer $r$ such that $$M^{k} \leq 2^r \lt M^{k+1}\quad?$$

-
This is uninterpretable, I’m afraid. What is $r$? Is $K$ the same as $k$? – Brian M. Scott Aug 13 '11 at 4:44
In addition, this was also posted over at Overflow. – mixedmath Aug 13 '11 at 4:54
@Theo: Done. I think that your interpretation is pretty clearly right, and it makes a very reasonable question. – Brian M. Scott Aug 13 '11 at 8:21
@Theo Done! Thanks for that - – mixedmath Aug 13 '11 at 8:26

The question is a variation on the well known fact that any real interval of length greater than $1$ contains at least one integer.

Hint: Assume that $a$ and $b$ are positive real numbers such that $b\ge 2a$. Then $a\le 2^r<b$, where $r=\max R$ with $$R=\{n\ \text{integer}\mid 2^n<b\}.$$ Of course, several things need to be checked before one can call this a proof, to begin with, that $a=M^k$ and $b=M^{k+1}$ is an admissible choice, that the set $R$ is non empty and indeed has a maximum...

After all this is done, one could check that $r'=\min R'$ works as well, with $$R'=\{n\ \text{integer}\mid 2^n\ge a\}.$$

-
+1. Simple questions should be given simple answers! (IMHO.) – Pierre-Yves Gaillard Aug 13 '11 at 9:22
@Pierre-Yves, thanks. Let us hope this constructive approach is what the OP is asking for. – Did Aug 13 '11 at 9:38
Welcome. In fact I would have defined $r$ as the least $n$ with $2^n\ge a$, or the greatest $n$ with $2^n < b$. – Pierre-Yves Gaillard Aug 13 '11 at 10:05
@Pierre-Yves, you know, I (reluctantly) admit you (might) have (kind of) a point here... :-) Thanks! Your version is definitely better, I revised my answer. – Did Aug 13 '11 at 10:48

The simplest way to state this is using the natural logarithm : the inequality $$M^k \le 2^r <M^{k+1}$$ is equivalent to $$k \log M \le r \log 2 < (k+1) \log M$$ and again equivalent to $$k \left( \frac{\log M}{\log 2} \right) \le r < (k+1) \left( \frac{ \log M}{ \log 2} \right).$$ which clearly has a solution because this is asking if there is an integer in the interval $[ k(\log M / \log 2), (k+1) ( \log M / \log 2 ) )$. It is possible because $M \ge 2$, hence the fraction of logarithms is greater than $1$ and the interval has length bigger than $1$.

Hope that helps,

-
Alternatively one could use the logarithm in base $2$ and see that nothing different happens. – Patrick Da Silva Aug 13 '11 at 12:04

Here’s another approach. Let $\lg x$ be the log base $2$ of $x$. If $M\ge 2$, then $\lg M \ge 1$, so $\lg M^{k+1} - \lg M^k = (k+1)\lg M - k\lg M = \lg M \ge 1$. That is, the length of the interval $\left[\lg M^k, \lg M^{k+1}\right)$ is at least $1$, so the interval must contain some integer $r$. Then $\lg M^k \le r < \lg M^{k+1}$, so ...?

Added: Though they look very different, this solution and Didier’s are actually very closely related. You might find it useful to try to see why his $r' = \lceil \lg M^k \rceil$, and his $r = \lfloor \lg M^{k+1} \rfloor$ unless $\lg M^{k+1}$ is an integer, in which case his $r = \lfloor \lg M^{k+1} \rfloor - 1$.

-