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

3 Answers 3

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$
1
  • $\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$ Aug 6, 2017 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.