Asintótica de la suma de $\sum_{j=1}^n j^{f(n)}$

Question

Lo que se sabe acerca de la asintótica de $\sum_{j=1}^n j^{f(n)}$ donde el exponente es alguna función que crece con $n$? Por ejemplo, si $f(n) = k$ es constante, entonces sabemos que es $\frac{1}{k+1}n^{k+1} + O(n^k)$. Si $f(n) = n$, parece que la suma es dominado por los últimos términos y se comporta como una serie geométrica con a$r=1/e$, de manera que la suma crece como $n^n\frac{e}{e-1}$ (además de algunas término de error). ¿Qué sucede si, por ejemplo, $f(n) = n^\alpha$ para $0 < \alpha < 1$ o $f(n) = \log n$?

Answer 1

(Nota: los cálculos en este post puede ser desactivado). Este es un ejemplo perfecto de Euler-Maclaurin fórmula que establece que:

$$ \sum_{j=1}^n f(j) \sim \int_1^n f(x) \ dx + \frac{f(1)+f(n)}2 + \sum_{k=1}^{\infty} \frac{B_{2k}}{(2k)!}(f^{(2k-1)}(n) - f^{(2k-1)}(1)).$$

Para obtener más información, consulte aquí. Si se utiliza esta fórmula para la función $f(x) = x^{\log(n)}$, se obtiene el siguiente enlazado: $$ \sum_{j=1}^n j^{\log(n)} = \frac{n^{\log(n) + 1}}{\log(n) + 1} + \frac{n^{\log(n)}}2 + O(\log(n) \ n^{\log(n)-1}). $$ I think all the other cases can be handled similarly assuming $f$ es suficientemente buena función.

Answer 2

(Ahora he reescrito esta 3 veces y, a pesar de que otra respuesta que se ha dado en entretanto, voy a presentar.)

Si vas a usar el de Euler-Maclaurin fórmula , usted necesita tener cuidado con el resto de plazo, asegurándose de no volar.

Deje $g(x) = x^{f(n)}$, entonces podemos escribir

\begin{align} F_f(n) &\equiv \sum_{j=1}^n j^{f(n)} = \sum_{j=1}^n g(j)\\ &= \underbrace{\int_0^n g(x)\;dx}_{(1)} + \underbrace{\sum_{k=1}^p \frac{B_k}{k!}\left(g^{(k-1)}(n) - g^{(k-1)}(0)\right)}_{(2)} +\underbrace{ R_p}_{(3)} \end{align}

(1) $$\int_0^n g(x)\;dx = \int_0^n x^{f(n)}\;dx = \frac{n^{f(n)+1}}{f(n)+1}$$

(2) Podemos inductivamente muestran que $g^{(k)}(x) = P_k(n)x^{f(n)-k}$ para una secuencia $\big(P_k(n)\big)_k$. Claramente $g(x)=g^{(0)}(x)=P_0(n)x^{f(n) - 0}$ donde $P_0(n)= 1$, y \begin{align} g^{(k)}(x) &= \frac{d}{dx} g^{(k-1)}(x) = \frac{d}{dx} P_{k-1}(n)x^{f(n)-(k-1)}\\ &= P_{k-1}(n)\big(f(n)-k+1\big) x^{f(n)-(k-1)-1} = P_k(n) x^{f(n)-k} \end{align} donde $P_k(n) \equiv P_{k-1}(n)\big(f(n)-k+1\big)$. Podemos calcular $$P_k(n) = P_{k-1}(n)\big(f(n)-k+1\big) = \prod_{j=0}^{k-1} \big(f(n)-j\big)$$

Por lo tanto \begin{align} \sum_{k=1}^p \frac{B_k}{k!}\left(g^{(k-1)}(n) - g^{(k-1)}(0)\right) &= \sum_{k=1}^p \frac{B_k}{k!}\left(P^{(k-1)}(n)n^{f(n)-k+1} - P^{(k-1)}(n)\cdot 0\right)\\ &= \sum_{k=1}^p \frac{B_k}{k!}n^{f(n)-k+1} \cdot\prod_{j=0}^{k-2}\big(f(n)-j\big) \end{align}

(3) Tenemos el siguiente límite en el resto término: \begin{align} |R_p| &\leq \frac{2\zeta(p )}{(2\pi)^p} \int_0^n |g^{(p )}(x)|\;dx = \frac{2\zeta(p )}{(2\pi)^p} \int_0^n |P_p(n)x^{f(n)-p}|\;dx\\ &\overset{(*)}{=} \frac{2\zeta(p )}{(2\pi)^p} |P_p(n)| \frac{n^{f(n)-p+1}}{f(n)-p+1} = \frac{2\zeta(p )}{(2\pi)^p} \prod_{j=0}^{p-2} \big(f(n)-j\big) n^{f(n)-p+1} \end{align}

en $(*)$ requerimos $f(n)\geq p$ de la integral converge.

En particular, si tomamos solamente 2 de los términos de (2) (que podemos hacer para evitar la $\zeta(1)$), entonces estamos obligados a la

\begin{align} |R_2| &\leq \frac{2\zeta(2)}{(2\pi)^2} \prod_{j=0}^{2-2} \big(f(n)-j\big) n^{f(n)-2+1} = \frac{2(\pi^2/6)}{4\pi^2} f(n) n^{f(n)-1}\\ % &= \frac{1}{12} f(n) n^{f(n)-1} \end{align}

Con $p=2$ escribimos \begin{align} F_f(n) % &= \frac{n^{f(n)+1}}{f(n)+1} + \sum_{k=1}^2 \frac{B_k}{k!}n^{f(n)-k+1} \cdot\prod_{j=0}^{k-2}\big(f(n)-j\big) + R_2\\ % &= \frac{n^{f(n)+1}}{f(n)+1} + \frac{(1 /2)}{1!}n^{f(n)-1+1} + \frac{(1 /6)}{2!}n^{f(n)-2+1}f(n) + R_2\\ % &= n^{f(n)}\left[\frac{n}{f(n)+1} + \frac{1}{2} + \frac{1}{12}\frac{f(n)}{n}\right] + R_2\\ \end{align}

Ejemplo 1 Para $f(n)=n$: $$F_f(n) = n^n\left[\frac{n}{n+1} + \frac{1}{2} + \frac{1}{12}\frac{n}{n}\right] + R_2 = n^n \left[\frac{19}{12} - \frac{1}{n+1}\right] + R_2$$

$$|R_2| \leq \frac{1}{12} n\cdot n^{n-1} = \frac{1}{12} n^n$$ así $$\lim_{n\to\infty} \frac{F_f(n)}{n^n} \in \left(\tfrac{19}{12}-\tfrac{1}{12}, \tfrac{19}{12} + \tfrac{1}{12}\right) = \left(\tfrac{3}{2}, \tfrac{5}{3}\right)$$

De hecho, un cheque: $$\frac{e}{e-1} \in (\tfrac{3}{2}, \tfrac{5}{3})$$

Ejemplo 2 Para $f(n)=\log(n)$: \begin{align} F_f(n) % &= n^{\log(n)}\left[\frac{n}{\log(n)+1} + \frac{1}{2} + \frac{1}{12}\frac{\log(n)}{n}\right] + R_2\\ % &= \frac{n^{\log(n)+1}}{\log(n)}\left[\frac{\log(n)}{\log(n)+1} + \frac{1}{2}\frac{\log(n)}{n} + \frac{1}{12}\left(\frac{\log(n)}{n}\right)^2\right] + R_2\\ \end{align}

\begin{align} |R_2| &\leq \frac{1}{12} f(n) n^{f(n)-1} = \frac{1}{12} \log(n) n^{\log(n)-1}\\ % &= \frac{1}{12} \frac{n^{\log(n)+1}}{\log(n)} \left(\frac{\log(n)}{n}\right)^2 \end{align}

Así $$\lim_{n\to\infty} \frac{F_f(n)}{\frac{n^{\log(n)+1}}{\log(n)}} = 1$$ debido a $\frac{|R_2|}{\frac{n^{\log(n)+1}}{\log(n)}} = \left(\frac{\log(n)}{n}\right)^2 \to 0$.

Ejemplo 3 $f(n) = n^\alpha$ para $\alpha\in(0,1)$:

\begin{align} F_f(n) % &=\frac{n^{n^\alpha+1}}{n^\alpha+1} + \frac{1}{2}n^{n^\alpha-1+1} + \frac{1}{12}n^{n^\alpha-1}n^\alpha + R_2\\ % &=\frac{n^{\alpha}}{n^\alpha+1}n^{n^\alpha+(1-\alpha)} + \frac{1}{2}n^{n^\alpha} + \frac{1}{12}n^{n^\alpha-(1-\alpha)} + R_2\\ \end{align}

$$|R_2| % \leq \frac{1}{12} f(n) n^{f(n)-1} = \frac{1}{12} n^{n^\alpha-(1-\alpha)}$$

$$\lim_{n\to\infty} \frac{F_f(n)}{n^{n^\alpha+(1-\alpha)}} = 1$$ como $$\frac{|R_2|}{n^{n^\alpha+(1-\alpha)}} = \frac{1}{12 n^{2(1-\alpha)}} \to 0$$

Ejemplo 4 Para $f(n)=n^\beta$, $\beta > 1$:

\begin{align} F_f(n) &=\frac{n^{f(n)+1}}{f(n)}\frac{f(n)}{f(n)+1} + \frac{1}{2}n^{f(n)} + \frac{1}{12}n^{f(n)-1}f(n) + R_2\\ &= n^{n^\beta - (\beta - 1)} \frac{n^\beta}{n^\beta+1} + \frac{1}{2}n^{n^\beta} + \frac{1}{12}n^{n^\beta+(\beta-1)} + R_2 \end{align}

$$|R_2| \leq \frac{1}{12} n^\beta n^{n^\beta-1} = \frac{1}{12} n^{n^\beta+(\beta-1)} $$

Por lo tanto $$\lim_{n\to\infty} \frac{F_f(n)}{n^{n^\beta+(\beta-1)}} \en \left(\tfrac{1}{12} - \tfrac{1}{12}, \tfrac{1}{12} + \tfrac{1}{12}\right) = \left(0, \tfrac{1}{6}\right)$$