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

  • Thread starter keniwas
  • Start date
  • #1
59
1

Main Question or Discussion Point

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.
 

Answers and Replies

  • #2
CRGreathouse
Science Advisor
Homework Helper
2,820
0
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.
 
  • #3
59
1
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]?
 
  • #4
236
0
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.
 
  • #5
695
2
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.
 
  • #6
105
0
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.
 

Related Threads for: Between two powers of an integer there is a power of two

  • Last Post
Replies
9
Views
7K
Replies
1
Views
2K
Replies
4
Views
4K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
15
Views
4K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
3
Views
6K
Top