10
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Regret May 5 '15 at 11:30
  • $\begingroup$ 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. $\endgroup$ – hxthanh May 5 '15 at 15:25
  • $\begingroup$ Example: Get $\delta(n)=0.6$ then wolframalpha.com/input/… $\endgroup$ – hxthanh May 5 '15 at 15:52
  • 1
    $\begingroup$ I'm sure this has been in the Fibonacci Quarterly. $\endgroup$ – marty cohen May 5 '15 at 20:14
  • $\begingroup$ What's the dollar sign? Is it superfluous? $\endgroup$ – Brian Tung May 5 '15 at 23:56
3
+100
$\begingroup$

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.)

enter image description here

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.

$\endgroup$
1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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 .. $\endgroup$ – Adrian Savage Aug 6 '17 at 20:25
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.