Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If we have

$$ S(n) = \sum_{k=1}^n \prod_{j=1}^k(1-\frac j n) $$

What the lower bound of $S(n)$ when $n\to\infty$?

PS: If I didn't make any mistake when I calculate $S(n)$, then it should be $\Omega(n)$. But I don't know how to get it.

share|improve this question
1  
Is $i=k$ ? (not enough characters) –  Phira Oct 10 '11 at 13:27
    
Oh yeah, I should be more careful about typos. –  ablmf Oct 10 '11 at 13:30
1  
It can be written alternatively as $\sum_{k=1}^{n}\frac{n!}{(n-k-1)!n^{k+1}}$ by expanding the product, if that helps at all. –  Arthur Oct 10 '11 at 14:07
    
@Sasha converted this into an integral and ask how to estimate that integral, there's some answers there too: math.stackexchange.com/questions/71447 –  Ragib Zaman Oct 10 '11 at 15:45

2 Answers 2

up vote 14 down vote accepted

We can do a bit better then a lower bound. We can find the main term, which is $\sqrt{\frac{\pi n}{2}}$.

Notice that $$\prod_{j=1}^{k}\left(1-\frac{j}{n}\right)=\frac{1}{n^{k}}\prod_{j=1}^{k}\left(n-j\right)=\frac{1}{n^{k}}\frac{(n-1)!}{(n-k-1)!}=\frac{\left(n-1\right)_{k}}{n^{k}}.$$ Using this, and the fact that the $k=n$ term is $0$, we can rewrite our series as

$$(n-1)!\sum_{k=1}^{n-1}\frac{1}{n^{k}(n-k-1)!}=\frac{(n-1)!}{n^{n-1}}\sum_{k=1}^{n-1}\frac{n^{n-k-1}}{(n-k-1)!}=\frac{(n-1)!}{n^{n-1}}\sum_{j=0}^{n-2}\frac{n^{j}}{j!}.$$

Where the last line follows from the substitution $j=n-k-1$. This last sum is the truncated exponential series with $x=n$. Specifically we have that $$\sum_{k=0}^{n-2}\frac{n^{k}}{k!}\sim \frac{1}{2}e^{n}.$$ Thus our series is $$\sim\frac{e^{n}(n-1)!}{2n^{n-1}}.$$ By Stirling's Formula, the main term is $$\frac{e^{n}(n-1)!}{n^{n-1}}=\sqrt{2\pi n}+O\left(\frac{1}{\sqrt{n}}\right),$$ so we are able to conclude that $$\sum_{k=1}^{n}\prod_{j=1}^{k}\left(1-\frac{j}{n}\right)\sim\sqrt{\frac{\pi n}{2}}.$$

Hope that helps,

Edit: A factor of two was missing earlier. Thanks to Didier Piau for pointing this out.

share|improve this answer
3  
Eric, nice proof. But we probabilists know that $\sum\limits_{k=0}^{n-2}\frac{n^k}{k!}\sim\frac12\mathrm e^n$. And Stirling's. –  Did Oct 10 '11 at 14:37
    
@DidierPiau: What exactly do you mean? –  Eric Naslund Oct 10 '11 at 14:50
    
Two things. First, $\sum\limits_{k=0}^{n-2}\frac{n^k}{k!}$ is not equivalent to $\mathrm e^n$ but to $\frac12\mathrm e^n$. Second, one should write Stirling's formula and not Stirlings formula. –  Did Oct 10 '11 at 14:57
    
@DidierPiau: Fixed now. Is there a clean way to get the asymptotic expansion of this series? To know the precise error terms, or better. I know it is equivalent to knowing an expansion for the incomplete Gamma Function $\Gamma(n,n)$. –  Eric Naslund Oct 10 '11 at 15:47
1  
@sigma, here is a sketch. The sum from $0$ to $n-2$ is equivalent to the sum from $0$ to $n$. The sum from $0$ to $n$, divided by $e^n$ is $A_n=\mathrm P(X_n\leqslant n)$ where the random variable $X_n$ is Poisson$(n)$. Thus $X_n$ is distributed like the sum of $n$ i.i.d. $Y_k$ Poisson$(1)$. The mean and the variance of $Y_k$ are both $1$ hence the CLT yields $A_n=\mathrm P((Y_1+\cdots+Y_n-n)/\sqrt{n}\leqslant0)\to\mathrm P(N(0,1)\leqslant0)=\frac12$. –  Did Oct 11 '11 at 8:50

This is $Q(n)-1$, where $Q(n)$ is a sum that appears repeatedly in Knuth's work and that I mention in my answer to your other question. A slight adaptation of the argument there shows that the dominant term is (in the notation of the answer) $T_n(0)$, and so we get $$Q(n) = S(n)+1 = \sqrt{\frac{\pi n}{2}} + O(1).$$ If you want a more precise asymptotic, you can check out Knuth's Art of Computer Programming, Vol. 1 (3rd ed.), Section 1.2.11.3 (again, as I mention in my other answer). He gives $$Q(n) = S(n)+1 = \sqrt{\frac{\pi n}{2}} - \frac{1}{3} + \frac{1}{12} \sqrt{\frac{\pi }{2n}} - \frac{4}{135n} + O(n^{-3/2}).$$

share|improve this answer
    
+1, very nice. Although I think the $\frac{1}{12}\sqrt{\frac{\pi n}{2}}$ term in the last expression should be changed. (Perhaps the $n$ should be removed?) –  Eric Naslund Oct 10 '11 at 15:49
    
@Eric: Thanks! Corrected. –  Mike Spivey Oct 10 '11 at 15:51
    
Curious question: Is the $\frac{1}{12}$ coming from the fact that in Stirling's formula we have the factor $\left(1+\frac{1}{12n}+\cdots\right)$? –  Eric Naslund Oct 10 '11 at 16:19
    
@Eric: Probably. There's an outline of a derivation using singularity analysis in "On Ramanjuan's Q-Function," by Flajolet, et al. See Theorem 2. I haven't worked through all the details, but right at the end they appear to be using Stirling's approximation to go from (in their notation) $[z^n] L(z)$ to the asymptotic for $Q(n)$. –  Mike Spivey Oct 10 '11 at 16:38

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.