I'm not sure how to evaluate the following :

$$ \sum_{k=i}^n \frac{1}{k!(n-k)!} $$

Where $i,n \in \mathbb{N}, n > i$ are given.

I don't have any working for this, I just looked it at and don't have any idea how to go about evaluating it.

  • 4
    $\begingroup$ You can at most write it as $\frac1{n!}\sum_{k=i}^n\binom{n}{k}$ but there is no closed form for it. $\endgroup$ – drhab Aug 30 '18 at 11:00
  • 1
    $\begingroup$ You have one in the case $i = 0$. $\endgroup$ – ncmathsadist Aug 30 '18 at 11:02
  • 2
    $\begingroup$ @ncmathsadist I think for $i=0$ the sum is $\frac{2^n}{n!}$ $\endgroup$ – Henry Aug 30 '18 at 11:02
  • 1
    $\begingroup$ @drhab - there may be a form related to the regularized incomplete beta function though this is may not be helpful $\endgroup$ – Henry Aug 30 '18 at 11:06
  • 1
    $\begingroup$ @Henry I see. It somehow shifts from sums to integrals (which can always be labeled with some name). $\endgroup$ – drhab Aug 30 '18 at 11:14

No Closed Form

As pointed out by @drhab, your sum is equivalent to $\frac{1}{n!}\sum_{k=i}^n\binom{n}{k}$. Given that $\sum_{k=0}^n\binom{n}{k}=2^n$, your sum can be rearranged to $$\frac{2^n}{n!}-\frac1{n!}\sum_{k=0}^{i-1}\binom{n}{k}$$

Hence, the partial sum of binomial coefficients, $\sum_{k=0}^{i-1}\binom{n}{k}$, is the heart of your problem. The sum can be expressed in various other ways (such as with hypergeometric or beta functions) and, as pointed out by @Henry, it has some nice expressions for specific $n,i$. But unfortunately, it has no closed form in terms of the sum of a fixed number of hypergeometric terms (Petrovsek, 1996. Theorem 5.6.3, pp. 88, 94, 102; 2, p. 6). But then again, it could possibly have a different type of closed form.

References and Further Reading

Despite having no closed form, the sum has been studied before and can be approximated and bounded:

  1. M. Petkovˇsek, G. S. Wilf and D. Zeilberger, 'A=B' (1996) (purchase eBook) (PDF)

  2. M. Boardman, 'The Egg-Drop Numbers' (2004) (link)

  3. Bounds and algorithms. (link)

  4. Approximations. (link)

  5. Asymptotics. (link)

  6. Relation to hyperplanes. (link)

  7. Wikipedia article. (link)


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.