# What's the lower bound of the sum $S(n) = \sum_{k=1}^n \prod_{j=1}^k(1-\frac j n)$?

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.

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

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.

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

-
+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