Beatty Sequences

Let r be a positive irrational number. Set s = 1/r, and define two sequences: a_n = n(r + 1) and b_n = 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 {a_n}∪{b_n} 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 {[a_n]} and {[b_n]} covers the set of natural numbers N = {1, 2, 3, ...}. It's a simple matter to show that Beatty's sequences {a_n} and {b_n} do not intersect. Therefore,

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 shed 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 a_n or b_n is integer,

Note that

(2)

.

Adding up (1) we thus get

which implies [N/(r + 1)] + [N/(s + 1)] = N - 1. Replacing N with N + 1, we see that exactly one term from the union {a_n}∪{b_n} is added. This naturally belongs to the interval (N, N + 1).

Let's see how the points a_n and b_n can 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 a_n+1 and a_n 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 a_n and b_m are adjacent, we may consider a linear combination αa_n + βb_n, where α, β > 0, and α + β = 1. All such combinations lie between a_n and b_m. In view of (2), we can take α = 1/(r + 1) and β = 1/(s + 1). The result - (n + m) - is an integer that lies between a_n and b_m.

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

Copyright © 1996-2012 Alexander Bogomolny

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

.

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

,

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

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

Copyright © 1996-2012 Alexander Bogomolny