Truncated alternating sum of binomial coefficients

166 Views Asked by At

Are there any nice counting arguments that identify the sum

$$S_{n,k} = {n \choose k} - {n \choose k-1} + {n \choose k-2} + \cdots + (-1)^k {n \choose 0}$$

with a simpler, more conceptually-appealing expression?

This expression comes up as the type of rank of a homology group of a somewhat complicated object and I'm hopeful I might be inspired by a counting argument.

1

There are 1 best solutions below

3
On BEST ANSWER

$$S_{n,k}=\binom{n-1}k.$$ Look at the subsets of $[n]=\{1,\ldots,n\}$ of size $\le k$, and pair off $A$ with $A\cup\{n\}$ for $A\subseteq[n-1]$. The unpaired sets are the $k$-element subsets of $[n-1]$.