Encontrar el más pequeño de k tal que $n^k > \sum_{i=0}^{n-1} i^k$

Question

Deje $n \in \mathbb{N}$. Es posible encontrar el más pequeño de $k \in \mathbb{N}$ tal que $$n^k > \sum_{i=1}^{n-1} i^k \ ?$$

---

Es fácil probar que tal se $k$ existen porque:

$$n^k > 1^k + 2^k + 3^k + 4^k + \dots + (n-2)^k + (n-1)^k$$ $$ \iff 1 > \left(\frac 1n\right)^k + \left(\frac 2n\right)^k + \left(\frac 3n\right)^k + \dots + \left(\frac {n-1}n\right)^k$$

Y puesto que todas las fracciones tiende a cero cuando $k \to \infty$, no debe ser una solución para $k$.

He intentado usar logartihms, pero yo no era capaz de hacer anythyng.

Entonces traté de encontrar el valor de la suma utilizando Faulhaber fórmula, pero la Faulhaber fórmula depende del exponente $k$ y ya no es fijo es casi inútil.

Cualquier otra manera de resolver esto?

Answer 1

Nota: Este post contiene sólo caracteres numéricos; véanse las respuestas por robjohn y Jack D'Aurizio de matemáticas.

Los cálculos numéricos muestran que $$k(n) = \lfloor n\log 2-0.039721\rfloor \quad \text{ for } \ 2\le n<944029$$ que es algo bueno. Sin embargo, esta fórmula empírica se rompe por $n=944029$. Lo que es peor, resulta que hay no $c$ tal que $k(n) = \lfloor n\log 2-c\rfloor$ tiene para todos los $n$. De hecho, hemos $$k(944029) = 654351, \quad \text{with } 944029\log(2)-654351 < 0.039717$$ $$k(603162) = 418079, \quad \text{with } \ 603162 \log 2 - 418079 > 1.0397208$$ Así, el rango de valores de $n\log 2-k(n)$ supera $1$, aunque sólo sea un poco.

Aún así, es razonable conjeturar que $$\lfloor n\log 2\rfloor-1 \le k(n) \le \lfloor n\log 2\rfloor \tag{??}$$ for all $n\ge 2$.

El límite superior fue demostrado por Jack D'Aurizio y por robjohn; también, robjohn dio un límite inferior que está muy cerca (??).

Answer 2

Usando la desigualdad $$ e^{-x/(1-x/k)}\le\left(1-\frac xk\right)^k\le e^{-x}\etiqueta{1} $$ y establecimiento $x=\frac{ik}{n}$ tenemos $$ \begin{align} \frac1{n^k}\sum_{i=0}^{n-1}i^k &=\frac1{n^k}\sum_{i=1}^n(n-i)^k\\ &=\sum_{i=1}^n\left(1-\frac in\right)^k\\ &\le\sum_{i=1}^ne^{-ik/n}\\ &\le\frac1{e^{k/n}-1}\tag{2} \end{align} $$ Por lo tanto, $k=\log(2)n$ es un límite superior.

Asumiendo $k/n$ es cerca de $\log(2)$, tenemos por cualquier $\alpha\gt0$, $$ \begin{align} \hspace{-1cm}\frac1{n^k}\sum_{i=0}^{n-1}i^k &=\frac1{n^k}\sum_{i=1}^n(n-i)^k\\ &=\sum_{i=1}^n\left(1-\frac in\right)^k\\ &\ge\sum_{i=1}^ne^{-ik/(n-i)}\\ &=\sum_{i=1}^ne^{-ik/n}-\sum_{i=1}^ne^{-ik/n}\left(1-e^{-i^2k/n/(n-i)}\right)\\ &\ge\color{#00A000}{\sum_{i=1}^ne^{-ik/n}}\color{#C00000}{-\sum_{i=1}^ne^{-ik/n}\frac{i^2k}{n(n-i)}}\\ &\ge\color{#00A000}{\sum_{i=1}^\infty e^{-ik/n}}\color{#C00000}{-\frac1{1-\alpha}\sum_{i=1}^{\alpha n}e^{-ik/n}\frac{i^2k}{n^2}-\sum_{i=\alpha n+1}^ne^{-ik/n}\frac{i^2k}{n}}\color{#00A000}{-\sum_{i=n+1}^\infty e^{-ik/n}}\\ &\ge\frac1{e^{k/n}-1}-\frac1{1-\alpha}\frac{k}{n^2}\frac{e^{-k/n}+e^{-2k/n}}{(1-e^{-k/n})^3}\color{#0000FF}{-e^{-\alpha k}\frac{nk}{e^{k/n}-1}-\frac{e^{-n}}{e^{k/n}-1}}\\ &\sim\frac1{e^{k/n}-1}-\frac{6\log(2)}{(1-\alpha)n}\tag{3} \end{align} $$ porque el azul términos de decaimiento exponencial.

Puesto que la derivada de $\frac1{e^x-1}$$x=\log(2)$$-2$, obtenemos $\frac1{e^{k/n}-1}-\frac{6\log(2)}{n}=1$ aproximadamente a las $k=\log(2)(n-3)$. Con un poco más de atención, vemos que con más precisión: $$ k=\log(2)(n-3)-\frac{3\log(2)(17\log(2)-6)}{2n}+\dots\etiqueta{4} $$ Por lo tanto, $k=\log(2)(n-3)$ es una buena estimación para el límite inferior.

---

La prueba de la Desigualdad

Desde $1+x\le e^x$$x\in\mathbb{R}$, tenemos $$ 1-\frac xk\le e^{-x/k}\le\frac1{1+\frac xk}=1-\frac{x}{k+x}\etiqueta{5} $$ Por lo tanto, $$ e^{-x/(k-x)}\le1-\frac xk\le e^{-x/k}\etiqueta{6} $$ Elevar a la $k^\text{th}$ de la potencia, $$ e^{-x/(1-x/k)}\le\left(1-\frac xk\right)^k\le e^{-x}\etiqueta{7} $$ como se desee.

Answer 3

Endeudamiento @Jason notación para: $$S_n(x)=\sum_{i=1}^{n-1}\left(\frac{i}{n}\right)^x$$ tenemos que: $$S_n(x)=-1+(1+1/n)^x\cdot S_{n+1}(x)\leq -1+e^{x/n}\cdot S_{n+1}(x),\tag{1}$$ así que para tener $S_n(x_n)<1$, es suficiente con que $S_{n+1}(x_n)<2\cdot e^{-x_n/n}$.

Ahora he estado, para después de la prueba: $$ 0<S_{n+1}(x)-S_{n}(x)<\frac{1}{x+1}\tag{2}.$$ La combinación de $(1)$ $(2)$ obtenemos: $$S_n(x)< -1+(1+1/n)^x\cdot\left(\frac{1}{x+1}+S_n(x)\right),$$ $$\frac{S_n(x)}{S_n(x)+\frac{1}{x+1}}<-1+(1+1/n)^x<e^{x/n}-1,$$

$$S_n(x) < \frac{e^{x/n}-1}{(2-e^{x/n})(x+1)}.\tag{3}$$

Ahora está claro que si $x$ es de alrededor de $n\log 2$ (cuánta distancia puede ser determinado mediante la resolución de $RHS=1$, es decir, $e^{x/n}=\frac{2x+3}{x+2}$ o $x=n\cdot\log\left(2-\frac{1}{x+2}\right)$, a través del método de Newton, por ejemplo) de la $RHS$ es de menos de $1$ y que se hacen:

$$ S_n\left(n\cdot \log\left(2-\frac{1}{n\log 2}\right)\right)<1\tag{4}$$

es una simple consecuencia de $(3)$; por otra parte, se va un poco más allá de la $n\cdot\log 2$-de la pared. Ahora probando que no podemos esperar a tener $S_n(x)<1$ $x$ muy por debajo de $n\cdot\log 2$ es sólo un ejercicio de las desigualdades-marcha atrás: sólo necesitamos un $\frac{C}{x+1}$ límite inferior para $S_{n+1}(x)-S_{n}(x)$ a reemplazar el lado izquierdo de $(2)$ (tal vez a través de la de Newton-Cotes de fórmulas con un cuantitativa término de error?). Por otra parte, ya sabemos que el $S_n(x)<1$ implica $x>\frac{2n}{3}-1$ por un straighforward de Riemann-sumas y convexidad argumento muestra por @127.0.9.6: sólo una pequeña pieza de trabajo que se necesita.

Answer 4

Yo estaba teniendo un poco de suerte por definir $$ S_n(x) = \sum_{i=1}^{n-1} \left(\frac{i}{n}\right)^x. $$

En el muy menos, consigue una justificación razonable para el $\log{2}$ coeficiente. Con un mínimo de álgebra, una ve $$ S_n(x) = \left(\frac{n-1}{n}\right)^x \left[1+S_{n-1}(x)\right]. $$

Definir $x_n$ tal que $S_n(x_n)=1$. Escribimos $x_{n}=x_{n-1}+\Delta_n$. Así, $$ S_n(x_n) = 1 = \left(\frac{n-1}{n}\right)^{x_n}\left[1+S_{n-1}(x_{n-1}+\Delta_n)\right] = \left(\frac{n-1}{n}\right)^{x_n}\left[2+\Delta_nS_{n-1}'(x_{n-1}) + O(\Delta_n^2)\right]. $$

La parte que no me gusta ahora es negar todo, pero supongo que los derivados de la $S_{n-1}$ son pequeñas en $x_{n-1}$. En cuyo caso, $$ x_n \approx \frac{\log{2}}{\log(n/(n-1))} = \frac{(n-1)\log{2}}{1+O(1/(n-1))} \approx (n-1)\log{2}. $$

Sin embargo, esto podría motivar a una perturbación de la solución de $x_n-x_{n-1} = \log{2}+O(\epsilon)$ o un límite de $\lim_{n\to\infty} (x_n-x_{n-1}) = \log{2}$.

Por lo tanto, no una solución completa, pero creo que es posible, vale la pena línea de argumento para seguir.