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.

  • 1
    Is $i=k$ ? (not enough characters)2011-10-10
  • 0
    Oh yeah, I should be more careful about typos.2011-10-10
  • 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.2011-10-10
  • 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.

  • 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.2011-10-10
  • 0
    @DidierPiau: What exactly do you mean?2011-10-10
  • 0
    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*.2011-10-10
  • 0
    @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)$.2011-10-10
  • 0
    The term $\frac12\mathrm e^n$ is a direct consequence of the central limit theorem. There is no interpretation as simple as this one (that I know of) for the next terms.2011-10-10
  • 0
    @EricNaslund: how did you get the summand $\frac{n^k}{k!}$?2011-10-10
  • 0
    @sigma.z.1980: You are right, that line is a bit brusque. I added an extra equation in the middle to help clarify.2011-10-10
  • 0
    @EricNaslund:all clear now, thanks2011-10-10
  • 0
    @DidierPiau: could you give a hint on how to approach this using CLT?2011-10-11
  • 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$.2011-10-11
  • 0
    @DidierPiau: excellent! Just 1 question: is $n-2$ 'equivalent' to $n$ in the sense 'equivalent for large $n$?2011-10-11
  • 0
    @sigma, no, and upon reflection, it is easier to consider $A_n=\mathrm P(X_{n}\leqslant n-2)$ and to note that $A_n=\mathrm P((Y_1+\cdots+Y_n-n)/\sqrt{n}\leqslant-2/\sqrt{n})$ hence $A_n\to\mathrm P(N(0,1)\leqslant0)=\frac12$.2011-10-11
  • 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
    +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?)2011-10-10
  • 0
    @Eric: Thanks! Corrected.2011-10-10
  • 0
    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)$?2011-10-10
  • 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