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?

• Just some observations: It looks like $\left|\sum\limits_{k=1}^n\left\{\frac k\varphi\right\}-\frac n2\right|<1$, and if you substitute $\sum\limits_{k=1}^n\left\{\frac k\varphi\right\}$ with $\frac n2$ in $A_n$, you get $B_n$ except without the floors. – Regret May 5 '15 at 11:30
• We're consider $B_n$ is equivalent to $B'_n=\left\lfloor \dfrac{n^2}{2\varphi}-\dfrac{n}{2\varphi^2}+\delta(n) \right\rfloor$ Here $0<\delta(n)<1$ and $\delta(n)$ can be constant. – hxthanh May 5 '15 at 15:25
• Example: Get $\delta(n)=0.6$ then wolframalpha.com/input/… – hxthanh May 5 '15 at 15:52
• I'm sure this has been in the Fibonacci Quarterly. – marty cohen May 5 '15 at 20:14
• What's the dollar sign? Is it superfluous? – Brian Tung May 5 '15 at 23:56

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.

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$

• The accepted answer is wrong, as can be seen with the increasing differences obtained by putting n = floor(phi^m/5) = 1 2 3 5 9 15 24 39 64 104 168 .. – Adrian Savage Aug 6 '17 at 20:25

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}$$