Compare $\sum_{k=1}^n \left\lfloor \frac{k}{\varphi}\right\rfloor$ ...
Solution 1:
Note that $$A_n = \sum_{k=1}^n\lfloor k(\phi - 1) \rfloor = S_n - \frac{1}{2}n(n+1),$$ where $S_n = \sum_{k=1}^n \lfloor k\phi \rfloor$ (appeared as A054347). In The Golden String, Zeckendorf Representations, and the Sum of a Series by Martin Griffiths, he showed that $S_n = \lfloor \frac{n(n+1)\phi}{2} - \frac{n}{2} \rfloor + \delta_1$, where $\delta_1 \in \{0,1\}$. Now, we have $$A_n = \left\lfloor \frac{n(n+1)\phi}{2} - \frac{n}{2} \right\rfloor + \delta_1 -\frac{1}{2}n(n+1) = \left\lfloor \frac{n^2}{2\phi} - \frac{n}{2\phi^2} \right\rfloor + \delta_1 = B_n - \delta_2 + \delta_1,$$ where $\delta_2\in\{0,1\}$, and so $|A_n - B_n|\le 1$.
Efficient Recursive Formula for $A_n$
The following picture gives you a way to express $A_n$ in a different way. (Indeed, it is just Fubini's theorem.)
Namely, the area of the staircase (red and orange region) is exactly $A_n$.
However, one can calculate the area of the staircase in a different way. Define $m = \lfloor n / \phi\rfloor$. The area of the staircase between $y = k-1$ and $y = k$ (where $k = 1, \dots, m$) is $n - \lfloor k\phi \rfloor$.
From this, we can get a formula for $A_m$, $$A_n = mn - \sum_{k=1}^m \lfloor k\phi \rfloor = mn - S_m.$$
On the other hand, $$A_m = \sum_{k=1}^m \lfloor k(\phi-1) \rfloor = S_m - \frac{1}{2}m(m+1).$$ Therefore, we obtain $$A_n + A_m = mn - \frac{1}{2}m(m+1).$$ Now one can compute $A_n$ in $O(\log n)$ time.
Solution 2:
The difference $A_n-B_n$ can be proven to have no fixed upper or lower bound.
Let $S_n = \sum_{k=1}^n \lfloor k\varphi \rfloor$
To calculate $S_n$ let $n'=\lfloor n\varphi\rfloor$ and $T_n = \sum_{k=1}^n \lfloor k\varphi^2 \rfloor$
$\lfloor k\varphi\rfloor$ and $\lfloor k\varphi^2 \rfloor$ are complementary Beatty sequences so $S_n+T_{n-n'}=\sum_{k=1}^{n'} k=\frac {n'}2(n'+1)$
Since $\lfloor k\varphi^2\rfloor=\lfloor k\varphi\rfloor+k$ so $T_n-S_n=\sum_{k=1}^n(\lfloor k\varphi^2\rfloor-\lfloor k\varphi\rfloor)=\frac n2(n+1)$
giving a recursive formula to find $S_n$.
Let $n=n_m=\lfloor\dfrac{L_m}{5}\rfloor$ where $L_m$ is the Lucas sequence $L_n=\varphi^n+\bar\varphi^n$ and $\bar\varphi=-1/\varphi$ . Then for $m\ge0$ we have, by inspection, $\lfloor n_m/\varphi\rfloor=n_{m-1}-1$ when $m\equiv 2\mod 4$ and $=n_{m-1}$ otherwise, which allows us to use the recursive formula to show by induction on m that:
if $m\equiv0\mod4$ then $5n=L_m-2$ and $50S_n = L_{2m+1}+L_{m+1}-5L_m-\frac{5m}{2}+8$
if $m\equiv1\mod4$ then $5n=L_m-1$ and $50S_n = L_{2m+1}+3L_{m+1}-5L_m+\frac{5(m-1)}{2}-8$
if $m\equiv2\mod4$ then $5n=L_m-3$ and $50S_n = L_{2m+1}-L_{m+1}-5L_m-\frac{5(m-2)}{2}+8$
if $m\equiv3\mod4$ then $5n=L_m-4$ and $50S_n = L_{2m+1}-3L_{m+1}-5L_m+\frac{5(m-3)}{2}+12$
Let $U_n$ be an approximation for $S_n$ in some sense, specifically with $U_n=\sum_{k=1}^n (k\varphi -\frac12)=\dfrac{\varphi n(n+1)-n}2$ and we can see that the difference $S_n-U_n$ is dominated by a term linear in $m$, with sign depending on whether $m$ is even. For example, in the case $m\equiv 0\mod 4$, then $5n=\varphi^m+\bar\varphi^m-2$ and it follows that
$50S_n=\varphi^{2m+1}+\varphi^{m+1}-5\varphi^m-\frac{5m}2+8-5\bar\varphi^m+\bar\varphi^{m+1}+\bar\varphi^{2m+1}$
$50U_n=\varphi^{2m+1}+\varphi^{m+1}-5\varphi^m+10-6\varphi-\bar\varphi^{m-1}-5\bar\varphi^m-\bar\varphi^{2m-1}$
$S_n-U_n=-\frac m{20}+$...(terms of lower degree)
If we define $C_n=\dfrac{n^2}{2\varphi}-\dfrac{n}{2\varphi^2}$ then $C_n$ differs from $B_n$ by no more than 1 and $C_n=\dfrac{\varphi(n^2+n)-(n^2+2n)}2$.
Now $A_n-C_n=S_n-U_n$ which has no upper or lower bound. $\Box$
Solution 3:
I can prove less; we have $$\frac {n^2 + n} {2 \varphi} - n < A_n \leqslant \frac {n^2 + n} {2 \varphi}$$ and $$\frac {n^2 - n/\varphi} {2 \varphi} - \frac {1} {2} < B_n \leqslant \frac {n^2 - n/\varphi} {2 \varphi}.$$ It follows that $$\frac {n (\varphi + 1 - 2 \varphi^2)} {2 \varphi^2} < A_n - B_n < \frac {(\varphi + 1) n} {2 \varphi^2} + \frac {1} {2}.$$ That is, we have $$- \frac {n} {2} < A_n - B_n < \frac {n + 1} {2}$$