15
$\begingroup$

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.

  • 0
    @Sasha converted this into an integral and ask how to estimate that integral, there's some answers there too: http://math.stackexchange.com/questions/71447/2011-10-10

2 Answers 2

15

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.

  • 0
    @DidierPiau: this implies as $n \to \infty \ \ -\frac{2}{\sqrt{n}} \to 0$ so I get $\Phi(x)$ anyway.2011-10-12
11

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

  • 0
    @Eric: Probably. There's an outline of a derivation using singularity analysis in "[On Ramanjuan's Q-Function](http://algo.inria.fr/flajolet/Publications/FlGrKiPr95.pdf)," 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)$.2011-10-10