Compare $\sum_{k=1}^n \left\lfloor \frac{k}{\varphi}\right\rfloor$ ... Given two integer sequences
\begin{equation*}
\displaystyle A_n=\sum_{k=1}^n \left\lfloor \frac{k}{\varphi}\right\rfloor ,
\end{equation*}
\begin{equation*}
B_n=\left\lfloor\dfrac{n^2}{2\varphi}\right\rfloor-\left\lfloor \dfrac{n}{2\varphi^2}\right\rfloor
\end{equation*}
here: $\quad\varphi=\dfrac{1+\sqrt{5}}{2}\quad$ (golden ratio)
Prove that: $|A_n-B_n|\leq 1.$

I realized that the difference between $A_n$ and $B_n$ is very small but the failure in finding an exact formula for $A_n$
Could you help me?

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.
