Use combinatorial proof to show that $\sum\limits_{k=m}^{n}\binom{k}{m}=\binom{n+1}{m+1}$.

Question

I am going through a self-teaching journey in mathematics. Right now I am reading Book of Proof, by Richard Hammack, and in the Chapter on Counting, I came across the following exercise:

Use combinatorial proof to show that $\sum\limits_{k=m}^{n}\binom{k}{m}=\binom{n+1}{m+1}$.

My proof was the following:

Suppose $m\leq n$ and let $S=\{0,1,2,\ldots,m,\dots,n\}$. Notice that $|S| = n+1$ and that the right hand side of the equation, by definition, is the number of subsets of order $m+1$ of $S$.

Now, we will count the numbers of subsets of order $m+1$ of $S$ in a different way: for every element $k$ of $S$ such that $m\leq k\leq n$ we count the number of subsets of order $m$ of $S$ such that, for every subset we construct, all elements are less than $k$. By construction, there are always $k$ numbers less than $k$ in $S$, therefore, there are $\binom{k}{m}$ such subsets.

For each of these subsets, it's union with $\{k\}$ is a different subset of order $m+1$ of $S$. Since $k$ could be any number in $[m,n]$, we have that $\sum\limits_{k=m}^{n}\binom{k}{m}$ counts all subsets of $S$ with order $m+1$.

Since the right-hand and left-hand sides are solutions to the same counting problem, we conclude they are equal. $\blacksquare$

I desperately need some feedback on my proof-writing skills. It feels like my argument is solid, but at the same time, my writing might be somewhat convoluted. I don't know if it is clear enough, not straightforward enough, or if I explained too much. How detailed should I be?

Feel free to be very critical. I wanna be able to write proofs acceptably.

Answer 1

I think that your proof is well written. Initially, I thought that your proof had a flaw in it, but then, I re-considered.

You are in effect partitioning the $~\binom{n+1}{m+1}~$ subsets into groups, where group $k$ has all such subsets whose largest element is $(k)$. This means that you have partitioned the subsets into non-intersecting groups whose union does equal all of the pertinent subsets.

The only possible criticism that I would offer is that at first, it was not immediately clear that your approach was valid. I had to do some thinking to realize that you were validly partitioning the $~\binom{n+1}{m+1}~$ subsets. So, your proof could (perhaps) be improved by making it crystal clear that your partitioning is valid (i.e. that the partitioning represents mutually exclusive groups whose union does comprise all possible subsets).

Personally, in such a situation, I (sometimes) assume that my target audience is high school students.

Answer 2

Yes. In short:

Let $S=[[0..n]]$ , a set of $n+1$ elements.

  For any $m: 0\leq m\leq n$, then $\binom{n+1}{m+1}$ counts the distinct subsets of $S$ of size $m+1$ .

Let $k: m\leq k\leq n$

  Then $\binom{k}{m}$ counts the distinct size $m+1$ subsets of $S$ whose largest element is $k$.   (Constructed by taking each of the subsets of $[[0..k-1]]$ then unionning with $\{k\}$).   The collection of these subsets, for all $k∈[[m..n]]$, therefore comprises all the subsets of S of size m+1.

The counts must therefore be equal.

$$\therefore\qquad\sum_{k=m}^n\dbinom k m ~=~\dbinom{n+1}{m+1}$$