Is there any good approximation for $\prod_{i=3}^k (n-i)$? $(n \gg k)$

Question

Is there any good approximation for $\prod_{i=3}^k (n-i)$? $(n \gg k)$

I know that $\prod_{i=3}^k (n-i) < \prod_{i=3}^k n = n^{k-2}$

Also a tighter upper bound is appreciated.

Answer 1

The exact value of the product is

$$\frac{\Gamma(n-2)}{\Gamma(n-k)} = \frac{(n-3)!}{(n-k-1)!}$$

You can use the stirling approximation for large n.

If n-k-1 is not large, you can calculate (n-k-1)! directly.

Answer 2

Using Peter's answer and Stirling approxiamtion, you end with $$e^{2-k} (n-3)^{n-\frac{5}{2}} (n-k-1)^{k-n+\frac{1}{2}}$$

Answer 3

Let us denote \begin{equation} {\mathcal I}_{n,k} := \prod\limits_{i=3}^k (n-i) \end{equation} Then the quantity ${\mathcal I}_{n,k}$ is a polynomial of order $k-2$ in $n$.We have: \begin{eqnarray} {\mathcal I}_{n,k} &:=& \sum_{l=0}^{k-2} n^{k-2-l} \cdot (-1)^l \sum\limits_{3 \le i_1 < i_2 < \dots < i_l \le k} \prod_{q=1}^l i_q \\ &=& n^{k-2} - C^{k-2}_1\frac{k+3}{2} n^{k-3} + C^{k-2}_2 \frac{3 k^2+17 k+28}{12} n^{k-4} - C^{k-2}_3 (k+3)\frac{k^2+ 5 k + 10}{8} n^{k-5} + \dots + (-1)^{k-3} \frac{k!}{2!}\left(H_k - \frac{3}{2}\right) n + (-1)^{k-2} \frac{k!}{2!} \end{eqnarray}

It would be interesting to work out all coefficients of that polynomial in closed form.

Answer 4

You can start by writing $$ \prod_{i=3}^{k}(n-i)=n^{k-2}\prod_{i=3}^{k}\left(1-\frac{i}{n}\right)=n^{k-2}\exp\left[\sum_{i=3}^{k}\log\left(1-\frac{i}{n}\right)\right]. $$ Now, you've said that $k\ll n$; thus $\frac{i}{n}\to0$ uniformly over $3\leq i\leq k$.

How you proceed from here really depends on a more precise relationship between $k$ and $n$; in any case, the fact that $\frac{i}{n}\to 0$ means that you can use the Taylor series $$ \log\left(1-x\right)=-x-\frac{x^2}{2}-\frac{x^3}{3}-\cdots,\qquad \lvert x\rvert<1, $$ to find new bounds.

For example: if you know that $k^3\ll n^2$, then $$ \sum_{i=3}^{k}\log\left(1-\frac{i}{n}\right)=-\sum_{i=3}^{k}\frac{i}{n}+O\left(\sum_{i=3}^{k}\frac{i^2}{n^2}\right)=-\frac{k^2+k-6}{2n}+O\left(\frac{k^3}{n^2}\right), $$ so that $$ \prod_{i=3}^{k}(n-k)=n^{k-2}\exp\left[-\frac{k^2+k-6}{2n}\right]\left(1+O\left(\frac{k^3}{n^2}\right)\right). $$ If you knew, for instance, that $k^4\ll n^3$, you could do something similar but using the first two terms of the Taylor series for $\ln(1-x)$; etc, etc.