# Asymptotic of sum $\sum_{j=1}^n j^{f(n)}$

What is known about the asymptotic of $$\sum_{j=1}^n j^{f(n)}$$ where the exponent is some function that grows with $$n$$? For instance, if $$f(n) = k$$ is constant, then we know it's $$\frac{1}{k+1}n^{k+1} + O(n^k)$$. If $$f(n) = n$$, it seems that the sum is dominated by the last few terms and behaves like a geometric series with $$r=1/e$$, so that the sum grows as $$n^n\frac{e}{e-1}$$ (plus some error term). What happens if e.g. $$f(n) = n^\alpha$$ for $$0 < \alpha < 1$$ or $$f(n) = \log n$$?

• do you mean f(n) or f(j) in the exponent? Dec 4, 2018 at 1:47

(Note the calculations in this post might be off). This is a perfect example of the Euler-Maclaurin formula which states that:

$$\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)).$$

For more information, see here. If we use this formula for the function $$f(x) = x^{\log(n)}$$, we get the following bound: $$\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$$ is a sufficiently nice function.

• hi Sandeep, I think the last term should be $(\log n) n^{\log (n) - 1}$? Dec 4, 2018 at 4:09
• Thanks, this formula seems to give a non-trivial expansion exactly when $f(n) = o(n)$. When $f(n)$ is on order $n$, I think the geometric series behavior is correct and for superlinear growth, I think the entire sum is dominated by the last term. Dec 4, 2018 at 4:10
• @norfair yea i think you are correct Dec 4, 2018 at 5:29

(I have now rewritten this 3 times and, though another answer has been given in the meantime, I'll still submit it.)

If you are to use the Euler-Maclaurin formula you need to be careful with the remainder term, ensuring it doesn't blow up.

Let $$g(x) = x^{f(n)}$$, then we can write

\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) We can inductively show that $$g^{(k)}(x) = P_k(n)x^{f(n)-k}$$ for a sequence $$\big(P_k(n)\big)_k$$. Clearly $$g(x)=g^{(0)}(x)=P_0(n)x^{f(n) - 0}$$ where $$P_0(n)= 1$$, and \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} where $$P_k(n) \equiv P_{k-1}(n)\big(f(n)-k+1\big)$$. We can compute $$P_k(n) = P_{k-1}(n)\big(f(n)-k+1\big) = \prod_{j=0}^{k-1} \big(f(n)-j\big)$$

Hence \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) We have the following bound on the remainder term: \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}

at $$(*)$$ we require $$f(n)\geq p$$ for the integral to converge.

In particular, if we only take 2 terms from (2) (which we do to avoid $$\zeta(1)$$), then we bound the

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

With $$p=2$$ we then write \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}

Example 1 For $$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$$ so $$\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)$$

Indeed, a check: $$\frac{e}{e-1} \in (\tfrac{3}{2}, \tfrac{5}{3})$$

Example 2 For $$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}

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

Example 3 $$f(n) = n^\alpha$$ for $$\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$$ as $$\frac{|R_2|}{n^{n^\alpha+(1-\alpha)}} = \frac{1}{12 n^{2(1-\alpha)}} \to 0$$

Example 4 For $$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)}$$

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

• Hi adfriedman, thank you for the detailed answer. Regarding your Example 4, I'm not sure you can conclude that the limit is in the open interval $(0, 1/6)$. In fact, I believe the limit will be 0 since heuristically it seems that $\lim_{n \to \infty} F_f(n)/n^{n^{\beta}} = 1$. In other words, the sum is dominated by just the last term. Dec 4, 2018 at 15:59