Is there a simpler (preferably closed-form) way to compute this sum of binomial coefficients?

142 Views Asked by At

From my years browsing math.SE, I've come to learn there's always some useful--albeit obscure--identity for every conceivable sum of combinatoric functions.

Mine is as simple as they come: $$S(n,m)=\sum _{k=0} ^m {n \choose k}$$ for $m \leq n$.

That is, a partial sum of binomial coefficients. Practically: the number of ways one can choose a subset of $m$ or fewer objects out of a set of $n$ objects.

Apologies if this is already answered elsewhere, but a search for "sum of binomial coefficients" turns up hundreds of permutations (no pun intended) of the question, none of which seem to be relevant to this specific case.

1

There are 1 best solutions below

2
On BEST ANSWER

$${n\choose n-m}{\mbox{$_2$F$_1$}(1,-m;\,1+n-m;\,-1)}$$

where $\mbox{$_2$F$_1$}$ is a hypergeometric function.

See also OEIS sequence A008949.