Between two powers of an integer there is a power of two

[keniwas]

Hi Everyone,

I am reading up on information theory, and every resource I have found on the topic which derives the form of entropy uses the following inequality as part of the proof.

Let [tex]n[/tex] be a fixed positive integer greater than 1. If [tex]r[/tex] is an arbitrary positive integer, then the number [tex]2^r[/tex] lies somewhere between two powers of [tex]n[/tex]. i.e. There exists a positive integer [tex]k[/tex] such that

[tex]n^k\leq 2^r < n^{(k+1)}[/tex]

However, none of them prove it and I am unclear how to do so. If anyone has any ideas on how to prove it, or topics I should look into which would make this inequality obvious I would really appreciate it.

 

[CRGreathouse]

This is true for arbitrary integer sequences, not just powers of n (provided it increases without bound, and has a small enough member -- but those are obviously true for powers). Find the smallest member less than or equal to r, then choose the next one.

 

[keniwas]

This is true for arbitrary integer sequences, not just powers of n (provided it increases without bound, and has a small enough member -- but those are obviously true for powers). Find the smallest member less than or equal to r, then choose the next one.

Sorry, could you explain a little by what you mean that it applies to arbitrary integer sequences as well? I am not clear why we want the smallest member less than or equal to [tex]r[/tex]?

 

[Tinyboss]

So pick [tex]r[/tex] and [tex]n[/tex] first. Now, look at [tex]2^r[/tex], and find the largest [tex]k[/tex] such that [tex]n^k\le2^r[/tex]. Then the inequality holds.

 

[dodo]

Here's a quick&dirty explanation. Dividing through by [tex]n^k[/tex] you get
[tex]1\leq \frac {2^r}{n^k} < n \quad\quad\quad \mbox{(1)}[/tex]

Now consider the binary representation of the fraction
[tex]\frac 1 {n^k}[/tex]

This is less than 1, so it will begin by 0.xxx... You can shift left the bits in this representation until a 1 comes into the integer part (making it 1.xxx...). This new number is now between 1 and 2 (possibly equal to 1, but definitely less than 2). Let [tex]r[/tex] be the number of bits you shifted; then the shifted number is the fraction in inequality (1); and it is between 1 and 2. Since [tex]n \ge 2[/tex], the inequality holds.

 

[boboYO]

another lazy way to see it is to take log to the base n of both sides, ,which reduces the question to finding a k such that


[tex]k \leq r \log_n 2< k+1 [/tex]

which is obviously possible.