Skip to main content
2 of 2
Added a little more explanation.
Jeremy Rickard
  • 35.2k
  • 2
  • 110
  • 151

A slightly less computational method is to note that both sides of the identity count the number of subsets of $\{1,\dots,n\}$ with fewer than $s$ elements. This is obvious for the left hand side. It's true for the right hand side because $2^{k-1}\pmatrix{n-k\\s-k}$ is the number of such subsets $S$ for which $k$ is minimal such that $|S\cup\{1,\dots,k\}|\geq s$, since such a subset $S$ is the union of an arbitrary subset of $\{1,\dots,k-1\}$ and a subset of size $s-k$ of $\{k+1,\dots,n\}$.

Jeremy Rickard
  • 35.2k
  • 2
  • 110
  • 151