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 n be a fixed positive integer greater than 1. If r is an arbitrary positive integer, then the number 2^r lies somewhere between two powers of n. i.e. There exists a positive integer k such that

n^k\leq 2^r < n^{(k+1)}

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

 

[Tinyboss]

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

 

[dodo]

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

Now consider the binary representation of the fraction
\frac 1 {n^k}

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 r 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 n \ge 2, 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


k \leq r \log_n 2< k+1

which is obviously possible.