December 2021

Summation of a Partial Beatty Sequence

 \sum_{i=1}^{n}\mathcal{B}_{r\in\mathbb{Z}}^i = \sum_{i=1}^{n}\lfloor ir \rfloor

A partial Beatty sequence is the sum of all the Integer portions of positive multiples between 1 and n of an Irrational number.

Raleigh-Beatty Theorem

Rayleigh’s theorem, states that a sequence, consisting of all the positive integers that are not in the sequence, is itself a Beatty sequence generated by a different irrational number.

For any Beatty \mathcal{B}_r^n sequence where r > 1 there exists a complementary sequence \mathcal{B}_s^n where s>1 is defined as \frac{1}{r}+\frac{1}{s}=1. The union of both sequences is the set of all Integers from 1 to n.

We can find an equation for s in terms of r.

\begin{align}
\begin{gather*}
\frac{1}{s} + \frac{1}{r} = 1 \\ \downarrow \\
\frac{1}{s} = 1 - \frac{1}{r} \\ \downarrow \\
\frac{1}{s} = \frac{r}{r} - \frac{1}{r} \\ \downarrow \\
\frac{1}{s} = \frac{r-1}{r} \\ \downarrow \\
s = \frac{r}{r-1}
\end{gather*}
\end{align}

The complement consists of all integers not in the sequence. For any sequence dividing the value by the equation will give you the index of the value that is less than N = \mathcal{B}_r^n. This allows us to find the last index of the complement because the last value of the complement is lower than that of the sequence. \lfloor \frac{\mathcal{B}_r^i}{s} \rfloor.

\lfloor ir \rfloor = \mathcal{B}_r^i \rightarrow \lfloor \frac{\mathcal{B}_r^i}{r} \rfloor = i-1

\mathcal{B}_r^n is the largest term in the sequence, dividing that by ‘r’ would give you the index of the sequence .

For clarity we will express the largest value of the sequence as N = \mathcal{B}_r^i , and the upper index of the complement as m = \lfloor N/s \rfloor.

\begin{align}
\begin{gather*}
N = \mathcal{B}_r^n\\ \\
m = \lfloor N/s \rfloor\\ \\
\sum_{i=1}^{n}\lfloor ir \rfloor + 
\sum_{j=1}^m
\lfloor js \rfloor = 
\frac{N^2 + N}{2}
\end{gather*}
\end{align}

Building up to the Solution

Since the union of any Beatty sequence and its complement will cover all the positive integers up to n. This leads to the realization that any Integer between 1 and n can be expressed at either \lfloor ir \rfloor or \lfloor j(r+1) \rfloor.

The sum of the sequence in question:

\begin{align}
S(n, r) = \sum_{i=1}^{n}\mathcal{B}_r^i
\end{align}

The sum of the complementary sequence:

\begin{align}
S(m, s) = \sum_{j=1}^{m}\mathcal{B}_s^j | s = \frac{r}{r-1}
\end{align}

By way of the Raleigh-Beatty Theorem, the two sums are equivalent to the sum of the Integers from 1 to the highest Beatty sequence value (\mathcal{B}_r^n). This can be rearrange to say; the sum of a Beaty sequence is equal to the difference sum of all the encompassed Integers and the sequence’s complement.

\begin{align}
\begin{gather*}
S(n,r) + S(n,s) =
\sum_{i=1}^Ni \\
\downarrow \\
S(n,r) = 
\sum_{i=1}^Ni - 
S(n,s) 

\end{gather*}
\end{align}

At this point we want to express the sum of the complement in terms of sum the original sequence. We will do this by extracting \mathcal{B}_r^i from \mathcal{B}_i^s. So we need to define a value for s, we will use \sqrt{2}.

Expressing the Complement in Terms of the Original

Starting with r and s (1), we assign a value to r.

\begin{align}
r = \sqrt{2}, s= \frac{r}{r-1}
\end{align}

Substitute r for \sqrt{2}

\begin{align}
s= \frac{\sqrt{2}}{\sqrt{2}-1}
\end{align}

Factor out \sqrt{2}

\begin{align}
\begin{gather*}
s= 1-\frac{\sqrt{2}(\sqrt{2}+1)}{(\sqrt{2}-1)(\sqrt{2}+1)} \\
\downarrow\\
s= \frac{2+\sqrt{2}}{1} \\
\downarrow\\
 s=2+\sqrt{2}
\end{gather*}
\end{align}

Whole integers can be brought out of the floor function.

\begin{align}
\begin{gather*}
\mathcal{B}_s^i = \lfloor is\rfloor=\lfloor i(2+\sqrt{2})\rfloor \\
\downarrow \\
\lfloor 2i+i\sqrt{2}\rfloor \\
\downarrow \\
2i+\lfloor i\sqrt{2}\rfloor \\
\end{gather*}
\end{align}

Express \mathcal{B}_s^i in terms of \mathcal{B}_r^i.

\begin{align}
\begin{gather*}
\text{since } \mathcal{B}_r^i=\lfloor i\sqrt{2}\rfloor \\ 
\downarrow\\
\mathcal{B}_s^i = \mathcal{B}_r^i + 2i
\end{gather*}
\end{align}

Recursive Function

Express the complement sum in terms of the original sum.

\begin{align}
\begin{gather*}
S(n,s)=
\sum_{i=1}^n \mathcal{B}_s^i\\
\downarrow\\
\sum_{i=1}^n(\mathcal{B}_r^i+2i) \\
\downarrow\\
\sum_{i=1}^n\mathcal{B}_r^i+\sum_{i=1}^n2i \\
\downarrow\\
\sum_{i=1}^n\mathcal{B}_r^i+2\sum_{i=1}^ni \\
\downarrow\\
S(n, r) + 2(\frac{n(n+1)}{2}) \\
\downarrow\\
S(n,s)=S(n, r) + n(n+1)

\end{gather*}
\end{align}

From (5) using (11)

\begin{align}
\begin{gather*}
S(n,r) =  
\sum_{i=1}^Ni -
S(m,s) \\
\downarrow \\
S(n,r) = 
\sum_{i=1}^Ni - S(m,r) - m(m-1)
\end{gather*}
\end{align}

Expressed as a recursive function.

\mathcal{S}(n, r)= 
\begin{cases}
0 \leq n \leq 1 & 1 \\
n > 1 & 
\sum_{i=1}^Ni - S(m,r) - m(m-1)
\end{cases}

External References

https://en.wikipedia.org/wiki/Beatty_sequence