1
$\begingroup$

$ \textbf{Question:} $ Prove that for all $ n, \; k \in \mathbb{N} $ $$ \displaystyle \sum_{j = k}^{n} \binom{j}{k} = \binom{n + 1}{k + 1} $$

I have successfully proved this formula using induction. The book also provides an alternative way using a combinatorial proof as following. We know that $ \displaystyle \binom{n + 1}{k + 1} $ counts the class of all $ (k + 1) $-elements subsets of the $ (n + 1) $-elements set. But this class of subsets may be partitioned into subclasses corresponding to $ j = k, k + 1, \dots, n $ as follows.

The subclass of subsets with largest element equal to $ k + 1 $ is counted by $ \displaystyle \binom{k}{k}, $ the subclass of subsets with largest element equal to $ k + 2 $ is counted by $ \displaystyle \binom{k + 1}{k}, \dots, $ and the subclass of subsets with largest element equal to $ n + 1 $ is counted by $ \displaystyle \binom{n}{k}. $ The identity in questionfollows by the extended addition rule.

Can someone help me understand the part in the pink box? Each subset in the big class has $ k + 1 $ elements from the binomial coefficient $ \displaystyle \binom{n + 1}{k + 1}, $ but I don't understand what they mean when they say "subsets with largest element equal to $ k + 1. $" If the element in each subset is something like "people," how can there be "largest element?"

$\endgroup$
  • 1
    $\begingroup$ As there are a finite number of elements in the set, we can impose a temporary arbitrary strict total order. For example, if the set was of people, we could order them by height, alphabetically, by age, by the order in which we first saw them, or however else. It is helpful to think of working with the set $\{1,2,3,\dots,n\}$ and the usual canonical order that we are used to. Any other finite set of $n$ elements can be put in bijection with $\{1,2,\dots,n\}$ and we can use an order which is preserved by the bijection going to our original set. $\endgroup$ – JMoravitz Aug 14 '16 at 0:19
  • 1
    $\begingroup$ You can label people from 1 to n. $\endgroup$ – Zack Ni Aug 14 '16 at 0:20
  • 1
    $\begingroup$ Combinatorics of $n$ objects can naturally be thought of as combinations of the natural numbers $1$ to $n$. $\endgroup$ – user334732 Aug 14 '16 at 9:51
1
$\begingroup$

The formulation largest element $k+1$ in the proof indicates that the specific $(n+1)$-element set \begin{align*} [n+1]:=\{1,2,3,\ldots,n+1\} \end{align*} is considered. Considering $[n+1]$ is consistent with the complete text in the proof and quite usual in the context of a combinatorial proof.

When looking at the series of the LHS of \begin{align*} \sum_{j=k}^n\binom{j}{k}=\binom{n+1}{k+1}\tag{1} \end{align*} the key observation is that $(k+1)$-element subsets of $[n+1]$ have a largest element, which is at least $k+1$ and at most $n+1$. We use this fact to partition the subsets with respect to their largest element.

If we consider the $(k+1)$-element subsets with largest element equal to $j+1$ with $k+1\leq j+1\leq n+1$, we keep the element $j+1$ fix in the $(k+1)$-element subset and have $\binom{j}{k}$ possibilities to select the remaining $k$ elements from $[j]$.

Summing up this way the number of $(k+1)$-element subsets results in the LHS of (1).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy