1
$\begingroup$

I'm trying to find an asymptotic expansion for the following sum:

$$\sum_{k=2}^{n}\frac{n!}{k\left(n-k\right)!}=\sum_{k=2}^{n}\left(\begin{array}{c} n\\ k \end{array}\right)\left(k-1\right)!$$

for large $n$. According to Maple, this sum is equivalent to:

$$\frac{n^{2}-n}{2}\,_{3}F_{1}\left(1,2,2-n;3;-1\right)$$

where $_{3}F_{1}$ is a special case of the generalized hypergeometric function. But on the internet I cannot find any asymptotic expansion of $_{3}F_{1}$, because most work focused on other cases, e.g. $_{2}F_{1}$. I think it could be easier to work directly on the original sum. But by searching in previous posts I cannot find the specific sum I'm interested in. Moreover, asymptotic approximations of $\left(\begin{array}{c} n\\ k \end{array}\right)$ do not look very useful since they do not work for $k\approx n$. Help would be very appreciated!

$\endgroup$
1
$\begingroup$

Can be done in a similar way to this. Let $k = n - k$ for convenience: $$S = \sum_{k = 2}^n \frac {n!} {k (n - k)!} = \sum_{k = 0}^{n - 2} \frac {n!} {(n - k) k!} = (n - 1)! \sum_{k = 0}^{n - 2} \frac 1 {k!} \frac 1 {1 - \frac k n}.$$ The main contribution comes from small values of $k$, and it is sufficient to use an approximation of the summand that holds for large $n$ and fixed $k$. The $i$th order term in the approximation will be simply $(k/n)^i$. Then the summation range in $S$ can be extended to infinity, and we get a complete asymptotic series for $S$: $$S \approx e (n - 1)! \sum_{i = 0}^\infty \frac {B_i} {n^i},$$ where $B_0 = 1, B_1 = 1, .\!.\!.$ are the Bell numbers.

$\endgroup$
  • $\begingroup$ Oh that's great! Now I see what you've done. So, just to explain better your derivation, first you used the Taylor expansion of $\frac{1}{1-x}$, where in our case $x=\frac{k}{n}$. This provides the terms $\left(\frac{k}{n}\right)^{i}$. Then you used the Dobinski's formula. In this way you got the Bell numbers. Very cool! Just a question: can we really say that $\sum_{k=0}^{n-2}\frac{k^{i}}{k!}\approx eB_{i}$ for every $i$, even though $n$ is finite? I would expect that for large $i$ this identity is not true anymore. $\endgroup$ – user2983638 May 11 '18 at 13:03
  • $\begingroup$ But clearly this is an asymptotic expansion, so $n$ should be large anyway, which probably answers my question. $\endgroup$ – user2983638 May 11 '18 at 13:09
  • 1
    $\begingroup$ I actually used $\approx$ in the asymptotic series sense: $$ \forall i_0 \geqslant 0 \enspace \frac S {e (n - 1)!} - \sum_{i = 0}^{i_0} \frac {B_i} {n^i} = o(n^{-i_0}), \quad n \to \infty.$$ It can be proved along the same lines as in the post I linked to. $\endgroup$ – Maxim May 11 '18 at 15:02
  • $\begingroup$ Thanks! I've also added an additional answer, where I show a numerical confirmation of your result. $\endgroup$ – user2983638 May 11 '18 at 16:10
0
$\begingroup$

$$\sum_{k=2}^{n}\binom{n}{k}(k-1)! = \sum_{k=2}^{n}\binom{n}{k}\int_{0}^{+\infty}x^{k-1}e^{-x}\,dx = \int_{0}^{+\infty}\frac{(1+x)^n-nx-1}{x}e^{-x}\,dx $$ is expected to behave like $\int_{0}^{+\infty}x^{n-1}e^{-x}\,dx = (n-1)!$ plus a perturbation due to the fact that $\frac{(1+x)^n-nx-1}{x}$ does not behave like $x^{n-1}$ in a right neighbourhood of the origin. More accurate approximations can be derived from Laplace's method.

$\endgroup$
  • $\begingroup$ Wow absolutely brilliant! Very concise and clear explanation. Many thanks! $\endgroup$ – user2983638 Mar 9 '17 at 14:06
  • $\begingroup$ More precisely, the sum is $\Theta((n - 1)!)$, but it's not asymptotically equivalent to $(n - 1)!$. I've added an answer. $\endgroup$ – Maxim May 9 '18 at 16:16
  • $\begingroup$ @Maxim Could you explain what is the $\Theta$ function you are mentioning? I also ran numerical simulations to check the Jack D'Aurizio's answer, and I have to say it seems correct. $\endgroup$ – user2983638 May 10 '18 at 12:11
  • $\begingroup$ It's "grows as": $f = \Theta(g)$ means $f = O(g) \land g = O(f)$. Consider that the last term in the original sum is asymptotically equivalent to $(n - 1)!$, and the next to last term is also a.e. to $(n - 1)!$; their sum cannot be a.e. to $(n - 1)!$. $\endgroup$ – Maxim May 10 '18 at 15:14
  • $\begingroup$ Ok, actually I only verified numerically that the series grows as $\left(n-1\right)!$ and not as $n!$ or $\left(n-2\right)!$. This means that I missed the coefficient $e\sum_{i=0}^{\infty}\frac{B_{i}}{n^{i}}$. $\endgroup$ – user2983638 May 11 '18 at 13:18
0
$\begingroup$

This is just a numerical confirmation of the result derived by Maxim. The figure below shows that Maxim's asymptotic series (red line, truncated to $i=10$ in this example) converges to the original series (blue line) for large $n$, and that both the series converge to Euler's number $e$. enter image description here

$\endgroup$
-1
$\begingroup$

You must be more specific. Do you want an asymptotic expansion for large $n$? if so, are you aware of Sterling formula to approximate $n!$ for large $n$? This should help you finding your answer.

$\endgroup$
  • $\begingroup$ Yes it's for large $n$. Since I'm summing over $k$, there is no other free parameter. I'm aware of the Stirling formula, but it doesn't look very useful to me. There are other approximations of $\left(\begin{array}{c} n\\ k \end{array}\right) $, but they hold for $n\gg k$. How should I treat the case when $k\approx n$? $\endgroup$ – user2983638 Mar 9 '17 at 11:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.