Beatty Sequences II

Assume $r\;$ and $s\;$ are two (strictly) irrational numbers that satisfy $\displaystyle\frac{1}{r}+\frac{1}{s}=1.\;$ Then the sequences $\{a_n\}=\{\lfloor nr\rfloor\;:n\in\mathbb{N}\}\;$ and $\{b_n\}=\{\lfloor ns\rfloor\;:n\in\mathbb{N}\}\;$ are complementary. In other words,

$\{a_n\}\cup\{b_n\} = \mathbb{N}\;$ and $\{a_n\}\cap\{b_n\} = \emptyset ,$

where $\mathbb{N}=\{1,2,3,\ldots\}.$

This is the statement of Beatty's theorem (1926) one proof of which was published in 1927 and has been reproduced elsewhere at this site.

Below is a slight modification of the proof posted by Dan Sitaru at the CutTheKnotMath facebook page.

Proof

Assume to the contrary that there are integers $n,m,q\;$ such that

$\begin{align} q&\lt mr\lt q+1\\ q&\lt ns\lt q+1, \end{align}$

which is the same as

$\displaystyle\begin{align} \frac{m}{q+1}&\lt \frac{1}{r}\lt \frac{m}{q}\\ \frac{n}{q+1}&\lt \frac{1}{s}\lt \frac{n}{q}. \end{align}$

Adding up we obtain $\displaystyle\frac{m+n}{q+1}\lt \frac{1}{r}+\frac{1}{s}\lt \frac{m+n}{q},\;$ or

$\displaystyle\frac{m+n}{q+1}\lt 1\lt \frac{m+n}{q},$

so that $q\lt m+n\lt q+1,\;$ which is impossible since both $m+n\;$ and $q\;$ have been assumed to be integers. This immediately implies that $\{a_n\}\cap\{b_n\} = \emptyset .$

Below any integer $N\;$ the two sequences have between them $\displaystyle\left\lfloor\frac{N}{r}\right\rfloor+\left\lfloor\frac{N}{s}\right\rfloor\;$ terms. Let's denote the two numbers as, say, $a(N)\;$ and $b(N).\;$ We have

$\displaystyle a(N)\lt \frac{N}{r}\lt a(N)+1\;$ and $\displaystyle b(N)\lt \frac{N}{s}\lt b(N)+1$

so that

$\displaystyle\frac{a(N)}{N}\lt\frac{1}{r}\lt\frac{a(N)+1}{N},\\ \displaystyle\frac{b(N)}{N}\lt\frac{1}{s}\lt\frac{b(N)+1}{N}.$

Adding up gives $\displaystyle\frac{a(N)+b(N)}{N}\lt 1\lt\frac{a(N)+b(N)+2}{N},\;$ or $a(N)+b(N)\lt N\lt a(N)+b(N)+2.$ Since all the quantities involved are integers, it follows that $N=a(N)+b(N)+1,\;$ or $a(N)+b(N)=N-1,\;$ the exact number of integer intervals up to and including $N.\;$ Thus every interval of with successive integer endpoints, say $[u,u+1],\;$ contains exactly one term of the union $\{a_n\}\cup\{b_n\}\;$ so that, indeed, $\{a_n\}\cup\{b_n\} = \mathbb{N}.$

71924438