Cómo mostrar$n=1+\sum_{k=1}^{n}\left\lfloor{\log_2\frac{2n-1}{2k-1}}\right\rfloor$ para cada número natural$n$.

Question

Al responder a una pregunta aquí me di cuenta de que:

$$n=1+\sum_{k=1}^{n}{\left\lfloor{\log_2\frac{2n-1}{2k-1}}\right\rfloor}$$

para cada número natural $n$.

He intentado demostrar que el uso de Legendre de la fórmula (forma alternativa), como en la respuesta se mencionó anteriormente, pero sin éxito.

Alguien puede ayudar?

Answer 1

No estoy muy bien informado acerca de la teoría de los números, así que yo no conozco ninguna manera de resolver este uso de Legendre de la fórmula (incluyendo su forma alternativa) o de cualquier otra cosa. Sin embargo, creo que lo que se muestra a continuación puede no ser tan "delicado" como podría ser, pero es correcto. He intentado hacerlo lo más simple y completa como sea posible, por lo que es posiblemente el más prolijo de lo necesario. Yo quería ayudar a asegurar que es comprensible no sólo para el OP, pero también alguien leyendo esto que quizás no tengan mucho conocimiento de la teoría de números.

Se pueden resolver mediante el uso de la inducción matemática. Tenga en cuenta que su solicitud de fórmula de

$$n = 1 + \sum_{k \, = \, 1}^{n} \left\lfloor \log_{2}\cfrac{2n - 1}{2k - 1} \right\rfloor \tag{1}\label{eq1} $$

obras para $n = 1$ como se hace, simplemente, $n = 1 + \left\lfloor \log_{2}\cfrac{2 - 1}{2 - 1} \right\rfloor = 1 + 0 = 1$. Supongamos que \eqref{eq1} funciona para todas las $n <= m$ para algún número natural $m$. Para demostrar que funciona para $n = m + 1$hay $3$ específicos cosas a tener en cuenta.

1. Ir de $n = m$ a $n = m + 1$ implica sumar un plazo adicional, con el término final siempre se $0$ como es de$\left\lfloor \log_{2}\cfrac{2m + 1}{2m + 1} \right\rfloor$.
2. Para cada término en ambas sumatorias, es decir, para $k = 1, 2, 3, \ldots, m$, el valor es no decreciente, es decir, $\left\lfloor \log_{2}\cfrac{2m + 1}{2k - 1} \right\rfloor \ge \left\lfloor \log_{2}\cfrac{2m - 1}{2k - 1} \right\rfloor$, since $\log_{2}$ es una función creciente.
3. Basado en las consideraciones anteriores, para demostrar que \eqref{eq1} funciona, Necesito mostrar que exactamente uno de los términos siempre aumenta por exactamente $1$.

Para cualquier $1 \leq k \leq m$,

$$\left\lfloor \log_{2}\cfrac{2m - 1}{2k - 1} \right\rfloor = j \tag{2}\label{eq2} $$

para algunos entero $j \ge 0$, significa que

$$2^j \leq \cfrac{2m - 1}{2k - 1} \lt 2^{j + 1} \tag{3}\label{eq3} $$

Nota el "$\leq$" sólo es necesario para $j = 0$, cosa que puede ser igual de "$\lt$" en lugar del numerador y el denominador de $\cfrac{2m - 1}{2k - 1}$ son enteros impares y, por lo tanto, su división no puede ser un número entero. De manera similar, tener en cuenta que si por cualquier específicos de $k$ obtenemos que

$$\left\lfloor \log_{2}\cfrac{2m + 1}{2k - 1} \right\rfloor = j + 1 \tag{4}\label{eq4} $$

entonces también tenemos que

$$2^{j + 1} \lt \cfrac{2m + 1}{2k - 1} \lt 2^{j + 2} \tag{5}\label{eq5} $$

Nota el aumento no será por más de $1$ as, incluso para $k = 1$, pasando de $2m - 1$ a $2m + 1$ no es suficiente para dicho incremento. Desde $2k - 1 \gt 0$, podemos multiplicar todo en tanto \eqref{eq3} y \eqref{eq5} por $2k - 1$ y combinar las $2$ ecuaciones a través de su común $2^{j + 1}$ valor para conseguir que

$$2m - 1 \lt 2^{j + 1}\left(2k - 1\right) \lt 2m + 1 \tag{6}\label{eq6} $$

Esto demuestra que $2^{j + 1}\left(2k - 1\right)$ debe ser el único entero par entre las $2$ enteros impares consecutivos de $2m - 1$ e $2m + 1$. Esta entero par es $2m$, $j + 1$ siendo el poder de $2$ de la factorización de esta entero par y $2k - 1$ siendo el impar parte del entero. Esto confirma que existe siempre una, y sólo una, valor que se incrementará $1$, ya que los pasos son reversibles. Como tal, esto significa que por el paso inductivo que \eqref{eq1} funciona para $n = m + 1$ , por lo que el acabado de la prueba por inducción.

Como un ejemplo, considere el caso de $n = 5$ ir $n = 6$, lo $2n - 1$ va de $9$ a $11$. El valor es $10 = 2 \times 5$. Por lo tanto, $j = 0$ aquí y $2k - 1 = 5$, lo $k = 3$. Esto indica que el $3$rd plazo, y no otro, va a aumentar por $1$, pasando de $0$ a $1$. En primer lugar, aquí están los términos de $n = 5$

\begin{align} 5 & = 1 + \left\lfloor \log_{2} \cfrac{9}{1} \right\rfloor + \left\lfloor \log_{2} \cfrac{9}{3} \right\rfloor + \left\lfloor \log_{2} \cfrac{9}{5} \right\rfloor + \left\lfloor \log_{2} \cfrac{9}{7} \right\rfloor + \left\lfloor \log_{2} \cfrac{9}{9} \right\rfloor \\ & = 1 + 3 + 1 + 0 + 0 + 0 \tag{7}\label{eq7} \end{align}

La próxima, aquí están los términos de $n = 6$

\begin{align} 6 & = 1 + \left\lfloor \log_{2} \cfrac{11}{1} \right\rfloor + \left\lfloor \log_{2} \cfrac{11}{3} \right\rfloor + \left\lfloor \log_{2} \cfrac{11}{5} \right\rfloor + \left\lfloor \log_{2} \cfrac{11}{7} \right\rfloor + \left\lfloor \log_{2} \cfrac{11}{9} \right\rfloor + \left\lfloor \log_{2} \cfrac{11}{11} \right\rfloor \\ & = 1 + 3 + 1 + 1 + 0 + 0 + 0 \tag{8}\label{eq8} \end{align}

Las líneas finales de \eqref{eq7} y \eqref{eq8} mostrar que, como se predijo, la $3$rd plazo es el único para el cambio, pasando por $1$ de $0$ a $1$.