4
$\begingroup$

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$?

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

2 Answers 2

2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ hi Sandeep, I think the last term should be $(\log n) n^{\log (n) - 1}$? $\endgroup$
    – zoidberg
    Dec 4, 2018 at 4:09
  • $\begingroup$ 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. $\endgroup$
    – zoidberg
    Dec 4, 2018 at 4:10
  • $\begingroup$ @norfair yea i think you are correct $\endgroup$ Dec 4, 2018 at 5:29
1
$\begingroup$

(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)$$

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – zoidberg
    Dec 4, 2018 at 15:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .