I have been reading Dr. Carl Wagner's book Basic Combinatorics, and I cannot wrap my head around a particular theorem. Someone else has asked a very similar question and accepted an answer, but I'm afraid I still don't understand.
As stated, the theorem runs thus:
For all $ n, \; k \in \mathbb{N} $
$ \displaystyle \sum_{j = 0}^{n} \binom{j}{k} = \displaystyle \sum_{j = k}^{n} \binom{j}{k} = \binom{n + 1}{k + 1} $
There follows a proof of the $\binom{n + 1}{k + 1} $ bit using some handy substitutions. What confuses me is the next part:
#2. Clearly $ \binom{n+1}{k+1} $ counts the class of all (k + 1)-element subsets of [n + 1]. But this class of k+1 subsets may be partitioned into subclasses corresponding to
j=k,k + 1, . . . ,nas follows.The subclass of subsets with largest element equal to k + 1 is counted by $ \binom{k}{k} $ (why?), the subclass of subsets with largest element equal to k + 2 is counted by $ \binom{k+1}{k} $ (why?), . . ., and the subclass of subsets with largest element equal to n + 1 is counted by $ \binom{n}{k} $ (why?).
I don't understand why at all! Indeed, it makes no sense to me.
It seems to me that the number of subsets of [n+1] with largest element k+1 would be $\binom{k+1}{k+1}$. Sure, that's the same as $ \binom{k}{k} $ since they both equal one, but that just seems to be a coincidence. We're choosing k+1 numbers from a set that runs from 1 to k+1. There can, naturally, be only one set that fits that bill. Yet to use $ \binom{k}{k} $ to represent that one set seems confusing to me, and every example that follows makes less sense.
What am I missing?
Best Answer
The largest element of a set has to be in the set. If you specify that $j+1$ is the largest element of a $(k+1)$-subset, it means that you have only $j$ choices $\{1,\dots,j\}$ for the remaining $k$ elements. The three examples given correspond to $j=k$, $j=k+1$, and $j=n$.