I need to find the n-th partial sum of:
$$\sum _{n=1}^x\lfloor n \sqrt{2}\rfloor$$
Or this sum of a Beatty sequence.
I tried to expand as the following:
$$=\frac{\sqrt{2} x \left(x+1\right)}{2}-\frac{x}{2}+\frac{1}{\pi }\sum _{n=1}^x\sum _{k=0}^{\infty}\frac{\sin \left(2 \pi \sqrt{2} k\ n\right)}{k}$$
$$=\frac{\sqrt{2} x \left(x+1\right)}{2}-\frac{x}{2}+\frac{1}{\pi }\sum _{n=1}^x \arctan (\tan( \frac{\pi – 2 \pi \sqrt{2} n}{2}))$$
For $ n ∈ \{0,\frac{1}{\sqrt{2}}\}$
$$=\frac{\sqrt{2} x \left(x+1\right)}{2}-\frac{x}{2}+\frac{1}{\pi }\sum _{n=1}^x \frac{\pi – 2 \pi \sqrt{2} n}{2}$$
But I still have the last term that oscillates around some value and I cant figure out how to find the result without doing the sum up to x. if there is no closed form, is it possible to find it for special values of x? Any hint is appreciated.
Best Answer
Since $\lfloor \sqrt 2 k \rfloor$ and $\lfloor (2+\sqrt 2) k \rfloor$ are complementary Beatty sequences, they partition the integers and we can find a recurrence relation for their sum. To sum the sequence $\lfloor \sqrt 2 k \rfloor$ we can use a well-known formula to add the consecutive integers $$ \begin{align} \sum_1^nk=&1+2+3+..+k+..+n\\ =&\frac{n(n+1)}2 \end{align} $$ and subtract the terms that should be missed. That is,
$$ \begin{align} &(1+2+4+..+\lfloor \sqrt 2 k \rfloor+..+\lfloor \sqrt 2 n \rfloor)\\ =&(1+2+3+..+k+..+\lfloor \sqrt 2 n \rfloor)\\ &-(3+6+..+\lfloor (2+\sqrt 2) k \rfloor+...+\lfloor (2+\sqrt 2) {n'} \rfloor)\\ =&(1+2+3+..+k+..+n^*)\\ &-2(1+2+..+k+...+n')\\ &-(1+2+4+..+\lfloor \sqrt 2 k \rfloor+...+\lfloor \sqrt 2 {n'} \rfloor)\\ \end{align} $$
where $n'=\lfloor (\sqrt 2-1) n \rfloor$ and $n^*=\lfloor \sqrt 2 n \rfloor$, giving us $$\sum_{k=1}^n\lfloor \sqrt 2 k \rfloor=\frac {n^*(n^*+1)}2 -n'(n'+1)-\sum_{k=1}^{n'} \lfloor \sqrt 2 k \rfloor$$ (Note that $n^*=n'+n$). Since the recurrence relation reduces the number of terms by a factor of $1+\sqrt 2$ on each iteration, we might be able to analyse this relation when $n$ is (near a multiple of) a power of $1+\sqrt2$ and come up with a closed formula for the sum. Let us define some integers for this purpose. Let $$ \begin{align} p_m&=\frac{(1+\sqrt 2)^m-(1-\sqrt 2)}{2\sqrt 2}^m\\ \text{and }q_m&=\frac{(1+\sqrt 2)^m+(1-\sqrt 2)}{2}^m \end{align} $$ Since $$ \begin{align} &p_0=0,\\ &p_1=q_0=q_1=1,\\ &p_m=2p_{m-1}+p_{m-2}\\ \text{and } &q_m=2q_{m-1}+q_{m-2},\\ \end{align} $$ then $p_m$ and $q_m$ are integers for each integer $m$.
As an example, we will take $n=q_m$ so $$ \begin{align} n'&=\lfloor (\sqrt2-1)n\rfloor\\ &=\lfloor \frac 12( \sqrt2-1)(1+\sqrt2)^m+\frac 12(\sqrt2-1)(1-\sqrt2)^m\rfloor\\ &=\lfloor \frac 12(1+\sqrt2)^{m-1}-\frac 12(1+\sqrt2)(1-\sqrt2)^m\rfloor+\sqrt2(1-\sqrt2)^m\rfloor\\ &=\lfloor \frac 12(1+\sqrt2)^{m-1}+\frac 12(1-\sqrt2)^{m-1}+\sqrt 2(1-\sqrt2)^{m}\rfloor\\ &=q_{m-1}+\lfloor \sqrt 2(1-\sqrt2)^{m}\rfloor\\ &=q_{m-1}+\begin{cases} 1, & \text{if $m=0$} \\ -1, & \text{if $m$ is odd} \\ 0, & \text{if $m>1$ and is even} \end{cases} \end{align} $$ The recurrence relation is now amenable to analytical tools because we have formulas that do not involve the floor function. Take $m>1$ for simplicity. Checking both even and odd $m$, we obtain the same recurrence formula in either case so $$ \begin{align} \sum_1^{q_m}\lfloor \sqrt2k\rfloor=&\frac{q_m(q_m+1)-q_{m-1}(q_{m-1}+1)}2\\ &+q_{m}q_{m-1}-\sum_1^{q_{m-1}}\lfloor \sqrt2n\rfloor \end{align} $$ This allows us to show by induction on $m$ that $$2\sum_{k=1}^{q_m}\lfloor \sqrt 2 k \rfloor=p_{2m}+q_{m-1}+(-1)^{m-1}$$