3
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ $f(n)=n^{n+o(n)}$. $\endgroup$
    – Did
    May 8, 2013 at 12:03
  • $\begingroup$ Thanks Didier - that certainly agrees with the data. Would you mind briefly sketching your reasoning? $\endgroup$
    – Granger
    May 8, 2013 at 12:38
  • $\begingroup$ Which context did you meet this beast in? $\endgroup$
    – Did
    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$
    – Granger
    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$ May 8, 2013 at 18:19

2 Answers 2

6
$\begingroup$

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

$\endgroup$
7
  • $\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$ 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$
    – GH from MO
    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$
    – GH from MO
    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$ May 9, 2013 at 11:58
  • $\begingroup$ And the error term is exponentially small. The Euler-Maclaurin formula will show it. $\endgroup$ May 9, 2013 at 12:05
-1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Didn't you took a $n$ for a $4$? The last term is $n^{-3n}$. $\endgroup$ 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$ May 8, 2013 at 15:21
  • 1
    $\begingroup$ The main contribution is around $i=n/(4\log n)$, not around $i=n$. $\endgroup$
    – Did
    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$
    – Granger
    May 8, 2013 at 15:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.