Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
$f(n)=n^{n+o(n)}$. –  Did May 8 '13 at 12:03
    
Thanks Didier - that certainly agrees with the data. Would you mind briefly sketching your reasoning? –  Granger May 8 '13 at 12:38
    
Which context did you meet this beast in? –  Did May 8 '13 at 15:44
    
It popped up in the analysis of an algorithm. According to Maple the corresponding integral can be expressed in terms of a Whittaker function. –  Granger May 8 '13 at 15:54
    
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. –  Tom Dickens May 8 '13 at 18:19
show 4 more comments

2 Answers

up vote 6 down vote accepted

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

share|improve this answer
    
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}))$. –  Johan Andersson May 9 '13 at 9:49
    
@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!$. –  GH from MO May 9 '13 at 10:18
    
@Johan: Note that for you version we need the refined Stirling's formula with explicit error term. –  GH from MO May 9 '13 at 10:20
    
Thanks everyone :) –  Granger May 9 '13 at 11:09
1  
I'm pretty sure the power of $4\ln n$ should be $n+1$ and not $n$. –  Brendan McKay May 9 '13 at 11:58
show 3 more comments

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

share|improve this answer
    
Didn't you took a $n$ for a $4$? The last term is $n^{-3n}$. –  Benoît Kloeckner May 8 '13 at 15:21
3  
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}.$$ –  Michael Renardy May 8 '13 at 15:21
1  
The main contribution is around $i=n/(4\log n)$, not around $i=n$. –  Did May 8 '13 at 15:48
    
@Michael: I think your observation will do nicely (having bounded the contribution of the tail $x > n$). Thanks! –  Granger May 8 '13 at 15:55
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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