# Find (recursive formulas for) $\sum_{k=1}^n\lfloor k\varphi\rfloor^2$ and/or $\sum_{k=1}^nk\lfloor k\varphi\rfloor$

I need to find $S_2(n)=\sum_{k=1}^n\lfloor k\varphi\rfloor^2$, where $\varphi$ is golden ratio. I use the approach used for $S(\alpha,n)=\sum_{k=1}^n\lfloor k\alpha\rfloor$, where $\alpha$ is arbitrary irrational, that can be found here (see Recursive formula in the 1st answer): Solve summation $\sum_{i=1}^n \lfloor e\cdot i \rfloor$

First, let $S_2(\alpha,n)=\sum_{k=1}^n\lfloor k\alpha\rfloor^2$, where $\alpha$ is an arbitrary irrational. We then need to find $S_2(\varphi,n)$.

For the first step in the approach mentioned above we have $\alpha=\varphi\in(1,2)$, hence we use Case 2 in the recursive formulas: $$S_2(\varphi,n)=\frac{(N-1)N(2N-1)}{6}-S_2(\beta(\varphi),n_1),$$ where $N=\lceil n\varphi\rceil$, $\beta(\varphi)=\frac{\varphi}{\varphi-1}=\varphi^2$, and $n_1=\lfloor\frac{N}{\beta(\varphi)}\rfloor=\lfloor\frac{N}{\varphi^2}\rfloor$.

At the second step, we need to evaluate $S_2(\varphi^2,n_1)$. Only thing is that $\varphi^2>2$, so we have Case 1 in the recursive formulas, which looks like this: $$S_2(\varphi^2,n_1)=\sum_{k=1}^{n_1}\lfloor k\varphi^2\rfloor^2=\sum_{k=1}^{n_1}\lfloor k(\varphi+1)\rfloor^2=\sum_{k=1}^{n_1}(k + \lfloor k\varphi\rfloor)^2=$$ $$=\sum_{k=1}^{n_1}(k^2+2k\lfloor k\varphi\rfloor+\lfloor k\varphi\rfloor^2)=\sum_{k=1}^{n_1}k^2+2\sum_{k=1}^{n_1}k\lfloor k\varphi\rfloor+S_2(\varphi,n_1).$$ I've no idea what to do with the middle sum.

I tried to bypass Case 1-situation by exploiting the fact that $\lfloor n\varphi^2\rfloor=\lfloor\lfloor n\varphi\rfloor\varphi\rfloor+1=A_{n,1}+1$, where $A_{n,1}$ can be found in the $n$-th row and 1st column of the Wythoff array. The Case-1 sum would then look like this $$S_2(\varphi^2,n_1)=\sum_{k=1}^{n_1}\lfloor k\varphi^2\rfloor^2=\sum_{k=1}^{n_1}(A_{n,1}+1)^2,$$ but I've no idea how to calculate numbers from the Wythoff array fast, let alone their squares. This may somehow be connected to the Zeckendorf representation, but I don't see how.

Any ideas? Thanks.

• Here we can exploit a result that does not hold in the $\lfloor en\rfloor$ case: $\lfloor \varphi n\rfloor$ is a Beatty sequence. – Jack D'Aurizio Nov 9 '17 at 16:23
• Do you mind quickly elaborating what you mean? I think I already use this fact at step 1, where I move from evaluation of $S_2(\varphi,n)$ to $S_2(\varphi^2,n_1), n_1<n$. – user75619 Nov 9 '17 at 16:41
• The frequency of such questions suggests that it's about an ongoing contest. – Professor Vector Nov 9 '17 at 18:42
• It's from one of those programming contest sites, yes, but it's not an ongoing contest. This one dates back to 5 years ago. No one who didn't solve it or come close to solving it would even recognize the problem, because these sums are the very final steps, which are not readily apparent from how the problem is formulated. – user75619 Nov 9 '17 at 20:08
• None of the sequences from the title belongs to The On-Line Encyclopedia of Integer Sequences (see here and here). – Alex Ravsky Nov 14 '17 at 0:51

A computational evidence suggests that $S_2(n)=\frac{\varphi^2}{3}n^3-\frac{1}{2}n^2+n I(n)$, where $|I(n)|<3$ and the graph of $I(n)$ looks like that of a Fourier series, see the sample for $1\le n\le 4096$
Similraly, $\sum_{k=1}^nk\lfloor k\varphi\rfloor=\frac{\varphi}{3}n^3-cn^2+nJ(n)$, where $c\simeq 0.5590$, $|J(n)|<4.5$ and the graph of $J(n)$ looks like that of a Fourier series, see the sample for $1\le n\le 4096$