Author |
Topic: beatty sequences and inverse sum (Read 1347 times) |
|
kiochi
Newbie
Posts: 42
|
 |
beatty sequences and inverse sum
« on: Jan 8th, 2007, 11:46am » |
 Quote  Modify
|
Sort of a cool relationship.
let a and b be postive reals, show
Each integer occurs exactly once in the sequence [a],[b],[2a],[2b],... (where [] is floor)
if and only if
1/a +1/b = 1 with a,b irrational.
|
| « Last Edit: Jan 8th, 2007, 1:57pm by kiochi » |
 IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender: 
Posts: 1261
|
|
Re: floor sequence and inverse sum
« Reply #1 on: Jan 8th, 2007, 1:44pm » |
Quote Modify
|
It's called the Beatty Sequence
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
kiochi
Newbie
Posts: 42
|
|
Re: beatty sequences and inverse sum
« Reply #2 on: Jan 8th, 2007, 2:03pm » |
Quote Modify
|
hmm so I guess this result is just "Beatty's theorem." I had fun proving it anyway when a friend brought it to me.
|
|
IP Logged |
|
|
|
kiochi
Newbie
Posts: 42
|
|
Re: beatty sequences and inverse sum
« Reply #4 on: Jan 10th, 2007, 11:27am » |
Quote Modify
|
actually that's only one direction 
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: beatty sequences and inverse sum
« Reply #5 on: Jan 11th, 2007, 12:20am » |
Quote Modify
|
A follow up: find the necessary and sufficient conditions for three real numbers a, b, c to cover the integers.
|
|
IP Logged |
|
|
|
kiochi
Newbie
Posts: 42
|
|
Re: beatty sequences and inverse sum
« Reply #6 on: Jan 11th, 2007, 7:00am » |
Quote Modify
|
on Jan 11th, 2007, 12:20am, Barukh wrote:| A follow up: find the necessary and sufficient conditions for three real numbers a, b, c to cover the integers. |
|
Actually, I think I can prove that it is impossible for the beatty sequences of three positive reals, a,b, and c to partition the natural numbers.
Maybe I'll hazzard a proof later today (when I have time), but if anyone beatts me to it that's fine, too.
|
|
IP Logged |
|
|
|
kiochi
Newbie
Posts: 42
|
|
Re: beatty sequences and inverse sum
« Reply #7 on: Jan 11th, 2007, 2:56pm » |
Quote Modify
|
on Jan 11th, 2007, 12:20am, Barukh wrote:| A follow up: find the necessary and sufficient conditions for three real numbers a, b, c to cover the integers. |
|
Actually, here are the necessary and sufficient conditions: one of a,b,c is zero (w.l.o.g. assume it is c), then it's just the condition in the above theorem, namely, 1/a+1/b = 1, with a,b irrational iff their beatty sequences... btw only one direction of that theorem has been posted (linked) above... anyone want to do the other... actually this result sort of spoils it.
Proof:
Suppose that a,b,c are positive real numbers s.t. their beatty sequences partition the set of natural numbers, N. w.l.o.g. assume a<b<c. (clearly they can't be equal). Clear also is that 1<a<2<b, 3<c, and no two of a,b,c can be rational (in fact the same arguments used in a proof, or at least my proof, of B's Theorem show that none of them are rational).
Let S_a={[na]:n in N}, and analagously define S_b and S_c.
Note that, for any positive integer n, [ka]<=n iff ka<n +1 iff k<(n+1)/a, so there are k=[(n+1)/a] elements of S_a less than or equal to n (and similarly for S_b and S_c). This shows that the density d(S_a) = limn-->infty [(n+1)/a]/n = 1/a. Likewise, the densities of S_b and S_c are 1/b and 1/c, respectively. Now, since they partition N, their densiities must add to the density of N, i.e.
1/a + 1/b +1/c = 1. (look familiar?)
Now as mentioned above c>3, so [c]>=3.
Set k = |{s in S_b : s<[c]}|.
Then |{s in S_a : s<[c]}| = [c]-k, so
([c]-k)a<[c] (in particular, note that 1/a>([c]-k)/[c]), so [([c]-k)a]<[c]-1, and [([c]-k+1)a]>[c], so
[c]>[([c]-k)a]=[([c]-k+1)a-a]>=[c]+1-2 (as a<2)
So [([c]-k)a]=[c]-1
This implies [kb]<[c]-1, so kb<[c]-1, so 1/b>k/([c]-1). Of course c<[c]+1, so 1/c>1/([c]+1). Adding these, we get an inequality:
1 = 1/a+1/b+1/c >([c]-k)/[c]+k/([c]-1)+1/([c]+1)
Multiplying through by the denoms and simplifying some things and getting everything on one side, we see this is equiv. to:
0>k[c]-[c]+[c]^2 +[c], now k,c>1, so this is all >[c]^2+[c] ... but [c]>1!!!
Contradiction!
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print