Compara $\sum_{k=1}^n \left\lfloor \frac{k}{\varphi}\right\rfloor$ ...

Question

Dadas dos secuencias de números enteros

\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*}

aquí: $\quad\varphi=\dfrac{1+\sqrt{5}}{2}\quad$ (proporción áurea)

Demuéstralo: $|A_n-B_n|\leq 1.$

---

Me di cuenta de que la diferencia entre $A_n$ y $B_n$ es muy pequeño, pero el fracaso en encontrar una fórmula exacta para $A_n$ ¿Podría ayudarme?

Answer 1

Tenga en cuenta que $$A_n = \sum_{k=1}^n\lfloor k(\phi - 1) \rfloor = S_n - \frac{1}{2}n(n+1),$$ donde $S_n = \sum_{k=1}^n \lfloor k\phi \rfloor$ (apareció como A054347 ). En La cuerda áurea, las representaciones de Zeckendorf y la suma de una serie por Martin Griffiths, demostró que $S_n = \lfloor \frac{n(n+1)\phi}{2} - \frac{n}{2} \rfloor + \delta_1$ donde $\delta_1 \in \{0,1\}$ . Ahora, tenemos $$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,$$ donde $\delta_2\in\{0,1\}$ y así $|A_n - B_n|\le 1$ .

Fórmula recursiva eficiente para $A_n$

La siguiente imagen le ofrece una forma de expresar $A_n$ de otra manera. (De hecho, es sólo el teorema de Fubini).

En concreto, el área de la escalera (región roja y naranja) es exactamente $A_n$ .

Sin embargo, se puede calcular el área de la escalera de otra manera. Defina $m = \lfloor n / \phi\rfloor$ . El área de la escalera entre $y = k-1$ y $y = k$ (donde $k = 1, \dots, m$ ) es $n - \lfloor k\phi \rfloor$ .

A partir de aquí, podemos obtener una fórmula para $A_m$ , $$A_n = mn - \sum_{k=1}^m \lfloor k\phi \rfloor = mn - S_m.$$

Por otro lado, $$A_m = \sum_{k=1}^m \lfloor k(\phi-1) \rfloor = S_m - \frac{1}{2}m(m+1).$$ Por lo tanto, obtenemos $$A_n + A_m = mn - \frac{1}{2}m(m+1).$$ Ahora se puede calcular $A_n$ en $O(\log n)$ tiempo.

Answer 2

La diferencia $A_n-B_n$ puede demostrarse que no tiene un límite fijo superior o inferior.

Sea $S_n = \sum_{k=1}^n \lfloor k\varphi \rfloor$

Para calcular $S_n$ deje $n'=\lfloor n\varphi\rfloor$ y $T_n = \sum_{k=1}^n \lfloor k\varphi^2 \rfloor$

$\lfloor k\varphi\rfloor$ y $\lfloor k\varphi^2 \rfloor$ son secuencias Beatty complementarias por lo que $S_n+T_{n-n'}=\sum_{k=1}^{n'} k=\frac {n'}2(n'+1)$

Desde $\lfloor k\varphi^2\rfloor=\lfloor k\varphi\rfloor+k$ así que $T_n-S_n=\sum_{k=1}^n(\lfloor k\varphi^2\rfloor-\lfloor k\varphi\rfloor)=\frac n2(n+1)$

dando una fórmula recursiva para encontrar $S_n$ .

Sea $n=n_m=\lfloor\dfrac{L_m}{5}\rfloor$ donde $L_m$ es la sucesión de Lucas $L_n=\varphi^n+\bar\varphi^n$ y $\bar\varphi=-1/\varphi$ . Entonces para $m\ge0$ que tenemos, por inspección, $\lfloor n_m/\varphi\rfloor=n_{m-1}-1$ cuando $m\equiv 2\mod 4$ y $=n_{m-1}$ en caso contrario, lo que nos permite utilizar la fórmula recursiva para demostrar por inducción en m que:

si $m\equiv0\mod4$ entonces $5n=L_m-2$ y $50S_n = L_{2m+1}+L_{m+1}-5L_m-\frac{5m}{2}+8$

si $m\equiv1\mod4$ entonces $5n=L_m-1$ y $50S_n = L_{2m+1}+3L_{m+1}-5L_m+\frac{5(m-1)}{2}-8$

si $m\equiv2\mod4$ entonces $5n=L_m-3$ y $50S_n = L_{2m+1}-L_{m+1}-5L_m-\frac{5(m-2)}{2}+8$

si $m\equiv3\mod4$ entonces $5n=L_m-4$ y $50S_n = L_{2m+1}-3L_{m+1}-5L_m+\frac{5(m-3)}{2}+12$

Sea $U_n$ sea una aproximación para $S_n$ en cierto sentido, concretamente con $U_n=\sum_{k=1}^n (k\varphi -\frac12)=\dfrac{\varphi n(n+1)-n}2$ y podemos ver que la diferencia $S_n-U_n$ está dominado por un término lineal en $m$ cuyo signo depende de si $m$ es par. Por ejemplo, en el caso $m\equiv 0\mod 4$ entonces $5n=\varphi^m+\bar\varphi^m-2$ y se deduce que

$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}+$ ...(términos de grado inferior)

Si definimos $C_n=\dfrac{n^2}{2\varphi}-\dfrac{n}{2\varphi^2}$ entonces $C_n$ difiere de $B_n$ por no más de 1 y $C_n=\dfrac{\varphi(n^2+n)-(n^2+2n)}2$ .

Ahora $A_n-C_n=S_n-U_n$ que no tiene límite superior ni inferior. $\Box$

Answer 3

Puedo probar menos; tenemos $$\frac {n^2 + n} {2 \varphi} - n < A_n \leqslant \frac {n^2 + n} {2 \varphi}$$ y $$\frac {n^2 - n/\varphi} {2 \varphi} - \frac {1} {2} < B_n \leqslant \frac {n^2 - n/\varphi} {2 \varphi}.$$ De ello se deduce que $$\frac {n (\varphi + 1 - 2 \varphi^2)} {2 \varphi^2} < A_n - B_n < \frac {(\varphi + 1) n} {2 \varphi^2} + \frac {1} {2}.$$ Es decir, tenemos $$- \frac {n} {2} < A_n - B_n < \frac {n + 1} {2}$$