Jtdylktuy

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^nfrac{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$?

(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.

(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+1big) 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+1big)$. We can compute
$$P_k(n) = P_{k-1}(n)big(f(n)-k+1big) = prod_{j=0}^{k-1} big(f(n)-jbig)$$

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 0right)\
&= sum_{k=1}^p frac{B_k}{k!}n^{f(n)-k+1} cdotprod_{j=0}^{k-2}big(f(n)-jbig)
end{align}

(3) We have the following bound on the remainder term:
begin{align}
|R_p|
&leq frac{2zeta(p )}{(2pi)^p} int_0^n |g^{(p )}(x)|;dx
= frac{2zeta(p )}{(2pi)^p} int_0^n |P_p(n)x^{f(n)-p}|;dx\
&overset{(*)}{=} frac{2zeta(p )}{(2pi)^p} |P_p(n)| frac{n^{f(n)-p+1}}{f(n)-p+1}
= frac{2zeta(p )}{(2pi)^p} prod_{j=0}^{p-2} big(f(n)-jbig) 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{2zeta(2)}{(2pi)^2} prod_{j=0}^{2-2} big(f(n)-jbig) n^{f(n)-2+1}
= frac{2(pi^2/6)}{4pi^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} cdotprod_{j=0}^{k-2}big(f(n)-jbig) + 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^nleft[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} ncdot n^{n-1} = frac{1}{12} n^n$$
so
$$lim_{ntoinfty} 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)^2right] + 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_{ntoinfty} 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 $alphain(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_{ntoinfty} 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_{ntoinfty} 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)$$