Series of binomial coefficient denominators

Question

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.

Answer 1

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)