Beatty Sequences

Let r be a positive irrational number. Set s=1/r, and define two sequences: an=n(r+1) and bn=n(s+1), n>0.

Obviously, all terms of both sequences are irrational. In particular, none of them is integer. A remarkable theorem discovered by Sam Beatty in 1926 states that, for any integer N, there is exactly one element from the union {an}∪{bn} that lies in the interval (N,N+1).

This property is very remarkable for the following reason. By definition, for a non-integer α, N<α<(N+1) is the same as ⌊α⌋=N. Thus Beatty's theorem asserts that the union of sequences of whole parts {⌊an⌋} and {⌊bn⌋} covers the set of natural numbers N={1,2,3,…}. It's a simple matter to show that Beatty's sequences {an} and {bn} do not intersect. But more than that, no two of their combined terms fall into the same interval (N,N+1), with N an integer:

{⌊an⌋}∪{⌊bn⌋}=N and {⌊an⌋}∩{⌊bn⌋}=∅,

which means that the sequences of whole parts complement each other in N. In this context, two sequences of integers that complement each other in N are called complementary, and Beatty's theorem shows a surprising way to generate such complementary sequences.

Let's prove Beatty's theorem. One elegant proof was published in 1927 by A. Ostrowski and A.C. Eitken The proof appears in Ross Honsberger's Ingenuity in Mathematics (MAA, 1970, pp 94-95.) While reading the book, I realized that Beatty's theorem is related to the problem of distribution of fractions on a unit interval that has been discussed elsewhere. In fact, Ostrowski and Eitken's proof was readily adaptable to the latter problem. It was then natural to ask whether the original proof for the problem of distribution of fractions might have bearings on Beatty's theorem.

Thinking along these lines led to a curious inequality that sheds some light on the distribution of Beatty's sequences on the number line.

Proof (Beatty's Theorem)

Let N be an integer. There are ⌊N/(r+1)⌋ terms of the first sequence less than N. There are ⌊N/(s+1)⌋ such terms from the second sequence. Since none of an or bn is integer,

N/(r+1)−1<⌊N/(r+1)⌋<N/(r+1)N/(s+1)−1<⌊N/(s+1)⌋<N/(s+1).

Note that

1r+1+1s+1=1r+1+11r+1=1r+1+rr+1=1.

Adding up (1) we thus get

N−2<⌊N/(r+1)⌋+⌊N/(s+1)⌋<N,

which implies ⌊N/(r+1)⌋+⌊N/(s+1)⌋=N−1. Replacing N with N+1, we see that exactly one term from the union {an}∪{bn} is added. This naturally belongs to the interval (N,N+1).

Note: elsewhere, there's another proof of Beatty's theorem.

Let's see how the points an and bn may be distributed on the number line. Mark all points of the two sequences. We are interested in the pairs of adjacent points. The distance between an+1 and an equals r+1, which is greater than 1. And the same is true for the second sequence. Which proves that between any two adjacent points that belong to the same sequence there's always an integer.

If, on the other hand, points an and bm are adjacent, we may consider a linear combination αan+βbn, where α,β>0, and α+β=1. All such combinations lie between an and bm. In view of (2), we can take α=1/(r+1) and β=1/(s+1). The result - (n+m) - is an integer that lies between an and bm.

|Contact| |Front page| |Contents| |Algebra| |Up|

Copyright © 1996-2018 Alexander Bogomolny

Sequences {an} and {bn} do not intersect. Indeed assume they have a common element: ai=bj, or explicitly: i(r+1)=j(s+1). Note that since rs=1,

r+1s+1=r+11r+1=r+1(r+1)/r=r.

Therefore, i(r+1)=j(s+1) would imply

r=r+1s+1=ji,

which, for an irrational r and rational j/i, is impossible.

|Contact| |Front page| |Contents| |Algebra| |Up|

Copyright © 1996-2018 Alexander Bogomolny