• Support PF! Buy your school textbooks, materials and every day products Here!

A proof needed

  • Thread starter Anzas
  • Start date
  • #1
88
0
prove that between any two real numbers there is a number of the form
[tex]\frac{k}{2^n}[/tex]
where k is an integer and n is a natural number.
 

Answers and Replies

  • #2
NateTG
Science Advisor
Homework Helper
2,448
5
This should be very easy.

Hint: Write the real numbers in binary.
 
  • #3
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,843
17
Sounds like homework. What have you tried?
 
  • #4
Icebreaker
Sounds interesting. I haven't been able to prove it, even with binary. :confused:
 
  • #5
HallsofIvy
Science Advisor
Homework Helper
41,738
899
I did something similar in a proof showing that monotone convergence implies least upper bound property.

Let the two distinct real numbers be a and b with a> b. Then a- b> 0 so [tex]\frac{1}{a-b}[/tex] exists and is positive. By the Archimedian property of integers (given any real number x, there exist an integer m with m>x) there exist an integer n with [tex]n> \frac{1}{a-b}[/tex].

But it is easy to prove by induction that, for all positive integers n, 2n> n (Hint: first prove by induction that 2n>= n+1) so we have [tex]2^n> \frac{1}{a-b}[/tex]. That means that 2n(a- b)= 2na- 2nb> 1.
Since the distance between those two numbers is greater than 1, there exist an integer, k, such that 2nb< k< 2na. Dividing through by 2n gives [tex]b< \frac{k}{2^n}< a[/tex].
 
Last edited by a moderator:
  • #6
NateTG
Science Advisor
Homework Helper
2,448
5
That's very elegant.

I was thinking more along the lines of:
WOLOG [itex]a>b[/itex].
Since [itex]a[/itex] and [itex]b[/itex] are real numbers, they can be written in binary notation in such a way that each of them has an infinite number of zeroes to the right of the binary (or is it still decimal?) point.

Now, since [itex]a \neq b[/itex] there is a first digit where they differ. At that position, [itex]a[/itex] will have a 1, and [itex]b[/itex] will have a zero. Now, since there is an infinite number of zeros, there is a next location where b has a zero. Let's say that that's the [itex]2^{-k}[/itex]s place.

Then the integer part of
[tex]b*2^{k}+1[/tex]
divided by
[tex]2^{k}[/itex]
Is between [itex]a[/itex] and [itex]b[/itex]
 

Related Threads for: A proof needed

  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
13
Views
1K
  • Last Post
Replies
0
Views
5K
  • Last Post
Replies
6
Views
2K
Replies
5
Views
5K
Replies
4
Views
2K
Replies
0
Views
1K
Top