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 \gt 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}\}\cup \{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 $\alpha,$ $N \lt \alpha \lt (N + 1)$ is the same as $\lfloor \alpha\rfloor = N.$ Thus Beatty's theorem asserts that the union of sequences of whole parts $\{\lfloor a_{n}\rfloor\}$ and $\{\lfloor b_{n}\rfloor\}$ covers the set of natural numbers $\mathbb{N} = \{1, 2, 3, \ldots\}.$ It's a simple matter to show that Beatty's sequences $\{a_{n}\}$ and $\{b_{n}\}$ 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:

$\{\lfloor a_{n}\rfloor\}\cup \{\lfloor b_{n}\rfloor\} = \mathbb{N}$ and $\{\lfloor a_{n}\rfloor\}\cap\{\lfloor b_{n}\rfloor\} = \emptyset ,$

which means that the sequences of whole parts complement each other in $\mathbb{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 $\lfloor N/(r + 1)\rfloor$ terms of the first sequence less than N. There are $\lfloor N/(s + 1)\rfloor$ such terms from the second sequence. Since none of $a_{n}$ or $b_{n}$ is integer,

(1)

$\begin{align}&N/(r + 1) - 1 \lt \lfloor N/(r + 1)\rfloor \lt N/(r + 1)\\ &N/(s + 1) - 1 \lt \lfloor N/(s + 1)\rfloor \lt N/(s + 1). \end{align}$

Note that

(2)

$\displaystyle\frac{1}{r+1}+\frac{1}{s+1}=\frac{1}{r+1}+\frac{1}{\displaystyle\frac{1}{r}+1}=\frac{1}{r+1}+\frac{r}{r+1}=1.$

Adding up (1) we thus get

$N - 2 \lt \lfloor N/(r + 1)\rfloor + \lfloor N/(s + 1)\rfloor \lt N,$

which implies $\lfloor N/(r + 1)\rfloor + \lfloor N/(s + 1)\rfloor = N - 1.$ Replacing $N$ with $N + 1$, we see that exactly one term from the union $\{a_{n}\}\cup\{b_{n}\}$ 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 $a_{n}$ and $b_{n}$ 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 $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 $\alpha a_{n} + \beta b_{n},$ where $\alpha , \beta \gt 0,$ and $\alpha + \beta = 1.$ All such combinations lie between $a_{n}$ and $b_{m}.$ In view of (2), we can take $\alpha = 1/(r + 1)$ and $\beta = 1/(s + 1)$. The result - $(n + m)$ - is an integer that lies between $a_{n}$ and $b_{m}.$

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

Copyright © 1996-2018 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$,

$\displaystyle\frac{r+1}{s+1}=\frac{r+1}{\displaystyle\frac{1}{r}+1}=\frac{r+1}{(r+1)/r}=r.$

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

$\displaystyle r=\frac{r+1}{s+1}=\frac{j}{i},$

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

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

Copyright © 1996-2018 Alexander Bogomolny

 63429291

Search by google: