Proof of $\left|\sum_{k=2}^n \lfloor k^{\varphi-1}\rfloor-B_n\right|\le 2$

Question

When I was trying approximate this sum $\displaystyle A_n=\sum_{k=2}^n\left\lfloor k^{\varphi-1}\right\rfloor$, where $\varphi=\frac{1+\sqrt 5}{2}$ is the golden-ratio, I found that $B_n=\left\lfloor \dfrac{n^\varphi}{\varphi}+\dfrac{n^{\varphi-1}-n}{2}\right\rfloor$ is a good approximation $A_n$. reference WolframAlpha Can you help me proving that $\left|A_n-B_n\right|\le 2$?

Answer 1

Lower Riemann sum $$\sum_{k=2}^{n-1} \phi \left(\frac{k}{n}\right)^{\phi-1} \frac{1}{n} \rightarrow \int_0^1 \phi x^{\phi-1} = [x^{\phi}]_{0}^1 = 1$$ Hence $$\sum_{k=2}^{n-1} \phi \left(\frac{k}{n}\right)^{\phi-1} \approx n$$ $$\sum_{k=2}^{n-1} k^{\phi-1} \approx \frac{n^{\phi}}{\phi}$$ $$\sum_{k=2}^{n} k^{\phi-1} \approx \frac{n^{\phi}}{\phi} + n^{\phi-1}$$

Similarly you can get: Upper Riemann sum $$\sum_{k=2}^{n} \phi \left(\frac{k}{n}\right)^{\phi-1} \frac{1}{n} \rightarrow \int_0^1 \phi x^{\phi-1} = [x^{\phi}]_{0}^1 = 1$$ Hence $$\sum_{k=2}^{n} \phi \left(\frac{k}{n}\right)^{\phi-1} \approx n$$ $$\sum_{k=2}^{n} k^{\phi-1} \approx \frac{n^{\phi}}{\phi}$$ $$\sum_{k=2}^{n} k^{\phi-1} \approx \frac{n^{\phi}}{\phi} $$

Using the average of Upper Riemann sum and Lower Riemann sum based expressions we get $$\sum_{k=2}^{n} k^{\phi-1} \approx \frac{n^{\phi}}{\phi} + n^{\phi-1}/2.$$

The approximation becomes accurage as $n \rightarrow \infty$.

The Error bound is $$\left|\frac{n^{\phi-1}}{\phi} \sum_{k=2}^n -n \int_{(k-1)/n}^{k/n} \phi x^{\phi-1} + \phi(k/n)^{\phi-1} - n^{\phi-1}/2 \right|$$ $$ = \left| \frac{1}{\phi} \sum_{k=2}^n -k^{\phi}+(k-1)^{\phi}+ \phi k^{\phi-1} - n^{\phi-1}/2 \right|$$

By mean Value theorem, for $h \in [k-1,k]$, $$\leq \left|\frac{1}{\phi} \sum_{k=2}^n -\phi h^{\phi-1}+ \phi k^{\phi-1} - n^{\phi-1}/2 \right |$$ For $h' \in [k-1,k]$ and it turns out we can use $h-k \approx 1/2$, $$\leq \left |\frac{1}{2}\frac{1}{\phi} \sum_{k=2}^n \phi (\phi-1)h'^{\phi-2} - n^{\phi-1}/2 \right |$$ Note that $\phi- 2 <0 $, $$\leq \left |\frac{1}{2} \times (\phi-1) \sum_{k=2}^n (k-1)^{\phi-2} - n^{\phi-1}/2. \right |$$ $$\leq \left|\frac{1}{2} (\phi-1) \left(\sum_{k=1}^{n-1} k^{\phi-2} - \frac{n^{\phi-1}}{(\phi-1)} \right) \right |$$

Approximately using $\phi-1 \approx 0.5$ and using $\sum_{k=1}^n \frac{1}{\sqrt{k}} \leq 2 \sqrt{n}$, $$\implies \sum_{k=1}^{n-1} k^{\phi-2} \approx \frac{n^{\phi-1}}{\phi-1}$$ Error seems to be less.

See if above is useful. Good Luck!

Answer 2

If you use, as @Gary suggested in comments, $$S_n=\sum\limits_{k = 2}^n {\left\lfloor {k^{\phi - 1} } \right\rfloor } \approx \sum\limits_{k = 2}^n {\left( {k^{\phi - 1} - \frac{1}{2}} \right)}=T_n $$ then $$T_n = H_n^{(1-\phi )}-\frac {n+1} 2$$ and, asymptotically, $$H_n^{(1-\phi )}=n^{\phi -1} \left(\frac{n}{\phi }+\frac{1}{2}+\frac{\phi-1 }{12 n}-\frac{(3-\phi ) (2-\phi) (\phi -1)}{720 n^3}+O\left(\frac{1}{n^4}\right)\right)+\zeta(1-\phi )$$ and $$\Delta_n=|S_n-T_n|$$ is quite small : for $2\leq n \leq 1000$, $\Delta_n^{\text{max}}=2.77$ while $S_{1000}=43706$.

Some numbers $$\left( \begin{array}{ccc} n & T_n & S_n \\ 10 & 23.0747 & 22 \\ 20 & 72.2587 & 71 \\ 30 & 141.157 & 140 \\ 40 & 226.888 & 226 \\ 50 & 327.692 & 327 \\ 60 & 442.338 & 442 \\ 70 & 569.894 & 569 \\ 80 & 709.625 & 709 \\ 90 & 860.926 & 861 \\ 100 & 1023.29 & 1024 \\ 200 & 3180.61 & 3182 \\ 300 & 6163.52 & 6163 \\ 400 & 9849.07 & 9850 \\ 500 & 14162.8 & 14163 \\ 600 & 19053.0 & 19052 \\ 700 & 24480.5 & 24481 \\ 800 & 30414.4 & 30415 \\ 900 & 36829.6 & 36828 \\ 1000 & 43704.7 & 43706 \\ \end{array} \right)$$

Considering $$T_n-\left(\dfrac{n^\phi}{\phi}+\dfrac{n^{\phi-1}-n}{2}-\frac 12\right)$$ it is asymptotic to $$\zeta(1-\phi )+\frac{1}{12\phi} n^{-\frac{3-\sqrt 5}{2} }$$

Edit

Counting $$\Delta_n=\left|\sum_{k=2}^n k^{\varphi-1}-\left\lfloor \dfrac{n^\varphi}{\varphi}+\dfrac{n^{\varphi-1}-n}{2}\right\rfloor\right|$$ for $2\leq n \leq 10000$

• $3$ appears $1002$ times (starting at $n=954$)
• $4$ appears $594$ times (starting at $n=1806$)
• $5$ appears $756$ times (starting at $n=5372$)

and so on.