Rayleigh's Theorem (Beatty's Theorem)

Theorem

Consider the sequence $\lfloor \alpha k \rfloor$ for $k \in \mathbb{Z}^+$, where $\alpha \in \mathbb{R}^+ \setminus \mathbb{Q}^+$ and $\alpha > 1$. For example, $[\sqrt{2}] \approxeq 1.414 = 1, [2 \sqrt{2}] \approxeq 2.828 = 2, [3 \sqrt{2}] \approxeq 4.242 = 4, [4 \sqrt{2}] \approxeq 5.656 = 5, [5 \sqrt{2}] \approxeq 7.071 = 7$ for $\alpha = \sqrt{2}$. Then, $[\alpha k]$ and $[\beta k]$ partitions an integer sequence if $\alpha^{-1} + \beta^{-1} = 1$. For example, $\frac{1}{\sqrt{2}} + \frac{1}{\sqrt{2}/(\sqrt{2} - 1)} = \frac{1}{\sqrt{2}} + \frac{\sqrt{2} - 1}{\sqrt{2}} = 1$. Which means $[\sqrt{2}/(\sqrt{2} - 1)] \approxeq 3.414 = 3, [2\sqrt{2}/(\sqrt{2} - 1)] \approxeq 6.828 = 6$.

Proof

The proof proceeds by contradiction, establishing two parts.

No Collision

Suppose some positive integer $v$ appears in both $\lfloor \alpha k \rfloor$ and $\lfloor \beta k \rfloor$.

Then there exist positive integers $r$ and $k$ such that $v = \lfloor \alpha r \rfloor = \lfloor \beta k \rfloor$.

This means $v \le \alpha r < v + 1$ and $v \le \beta k < v + 1$.

Dividing by $\alpha$ and $\beta$ respectively gives $\frac{v}{\alpha} \le r < \frac{v+1}{\alpha}$ and $\frac{v}{\beta} \le k < \frac{v+1}{\beta}$.

Note that equality cannot hold since $\alpha$ and $\beta$ are irrational.

Adding the two inequalities gives $\frac{v}{\alpha} + \frac{v}{\beta} = v!\left(\frac{1}{\alpha} + \frac{1}{\beta}\right) = v < r + k < \frac{v+1}{\alpha} + \frac{v+1}{\beta} = (v+1)!\left(\frac{1}{\alpha} + \frac{1}{\beta}\right) = v + 1$.

So $v < r + k < v + 1$, which contradicts $r + k$ being an integer.

Full Coverage

Suppose some positive integer $v$ does not appear in either $\lfloor \alpha k \rfloor$ or $\lfloor \beta k \rfloor$.

Then there exist positive integers $r$ and $k$ such that $\lfloor \alpha r \rfloor = v - 1$, $\lfloor \alpha(r+1) \rfloor = v + 1$, $\lfloor \beta k \rfloor = v - 1$, $\lfloor \beta(k+1) \rfloor = v + 1$.

This gives $\alpha r < v$, $\alpha(r+1) \ge v + 1$, $\beta k < v$, $\beta(k+1) \ge v + 1$.

Again, equality cannot hold since $\alpha$ and $\beta$ are irrational.

By dividing $\alpha, \beta$, it results in $r < \frac{v}{\alpha}, r + 1 > \frac{v + 1}{\alpha}, k < \frac{v}{\beta} , k + 1 > \frac{v + 1}{\beta}$.

Adding the 1st and 3rd inequalities: $r + k < \frac{v}{\alpha} + \frac{v}{\beta} = v$.

Adding the 2nd and 4th inequalities: $r + 1 + k + 1 > \frac{v+1}{\alpha} + \frac{v+1}{\beta} = v + 1$, so $r + k > v - 1$.

Combining: $v - 1 < r + k < v$, which contradicts $r + k$ being an integer.

Therefore, the claim holds. $\square$