I hope this question is not too simple, but I would like to know the asymptotic behaviour of the following function $f: \mathbb{N}^{+} \rightarrow \mathbb{Q}$ where $$ f(n) = \sum_{i=1}^{n} \frac{i^n}{n^{4i}} $$ Any references, pointers, or answers would be most appreciated.
$\begingroup$
$\endgroup$
9
-
1$\begingroup$ $f(n)=n^{n+o(n)}$. $\endgroup$– DidCommented May 8, 2013 at 12:03
-
$\begingroup$ Thanks Didier - that certainly agrees with the data. Would you mind briefly sketching your reasoning? $\endgroup$– GrangerCommented May 8, 2013 at 12:38
-
$\begingroup$ Which context did you meet this beast in? $\endgroup$– DidCommented May 8, 2013 at 15:44
-
$\begingroup$ It popped up in the analysis of an algorithm. According to Maple the corresponding integral can be expressed in terms of a Whittaker function. $\endgroup$– GrangerCommented May 8, 2013 at 15:54
-
$\begingroup$ You should be able to get this with the Laplace method for sums - find the dominant term, convert the Riemann sum to an integral of the form $\int dx \exp(f(x-x_0)) $ and use Laplace's method to estimate the integral. See Bender and Orszag's book for an example. $\endgroup$– Tom DickensCommented May 8, 2013 at 18:19
|
Show 4 more comments
2 Answers
$\begingroup$
$\endgroup$
7
From the comments so far (including mine above) it follows that $$ f(n) = \sum_{i=1}^{n} \frac{i^n}{n^{4i}}=\frac{n!}{(4\ln n)^{n+1}}\left(1+O(n^{-1/2}\ln n)\right). $$
answered May 9, 2013 at 7:59
-
$\begingroup$ and by Stirling's formula this gives us $f(n)=\sqrt{2 \pi n} (\frac{n}{4e \ln n})^n (1+O(n^{-1/2}))$. $\endgroup$ Commented May 9, 2013 at 9:49
-
$\begingroup$ @Johan: Yes. In fact the error term I indicated comes from Stirling's formula. Either way, you have to compare $(n/e)^n$ with $n!$. $\endgroup$ Commented May 9, 2013 at 10:18
-
$\begingroup$ @Johan: Note that for you version we need the refined Stirling's formula with explicit error term. $\endgroup$ Commented May 9, 2013 at 10:20
-
1$\begingroup$ I'm pretty sure the power of $4\ln n$ should be $n+1$ and not $n$. $\endgroup$ Commented May 9, 2013 at 11:58
-
$\begingroup$ And the error term is exponentially small. The Euler-Maclaurin formula will show it. $\endgroup$ Commented May 9, 2013 at 12:05
$\begingroup$
$\endgroup$
4
$f(n) = n^n 4^{-4n} (1 + O(n^{-4}))$. The sum is strongly dominated by its last term. I hope this isn't homework.
Apologies. I misread the question exact as Benoît suggests.
answered May 8, 2013 at 15:05
-
$\begingroup$ Didn't you took a $n$ for a $4$? The last term is $n^{-3n}$. $\endgroup$ Commented May 8, 2013 at 15:21
-
3$\begingroup$ The last term is $n^{-3n}$, which is certainly not dominant! The asymptotics is probably obtainable by comparing with $$\int_0^\infty x^n n^{-4x}\,dx=\frac{n!}{(4\ln n)^n}.$$ $\endgroup$ Commented May 8, 2013 at 15:21
-
1$\begingroup$ The main contribution is around $i=n/(4\log n)$, not around $i=n$. $\endgroup$– DidCommented May 8, 2013 at 15:48
-
$\begingroup$ @Michael: I think your observation will do nicely (having bounded the contribution of the tail $x > n$). Thanks! $\endgroup$– GrangerCommented May 8, 2013 at 15:55