Combinatorial proof of identity [closed]

Question

The following admits of many (easy) proofs, but I am seeing no purely "bijective" argument:

$$ \sum_{j=n}^N \binom{j}{n} = \binom{N+1}{n+1}. $$

Any ideas?

Answer 1

Santa Claus has $N+1$ reindeer whose noses are of varying redness. Every year, Santa needs $n+1$ reindeer to pull his sleigh. The reddest-nosed reindeer always leads the sleigh.

The way Santa chooses the reindeer is as follows. First, Santa chooses one reindeer to lead the sleigh; call it the $(j+1)$th reindeer. Then out of the $j$ reindeer whose noses are less red, Santa chooses $n$ more reindeer to complete the team.

One year, Santa learns (on MistletOverflow) that he can simply choose $n+1$ reindeer, and then see which of them has the reddest nose.

Answer 2

The definitions of finite sums, products and unions are inductive. Due to this, the various algebraic/inductive/bijective proofs (especially the elementary ones) of certain identities (particularly binomial ones) can often be viewed as the same proof with the definitions and/or steps done in different orders. This is a (not that deep) realization I've had from time to time. Ill spell it out a bit for my own satisfaction.

Your identity has two parameters so can be tackled various ways. I am not totally sure exactly what you are thinking of as the "usual proof." I will take that as license and first say that you suggest thinking of the summands as values from Pascals triangle, an array of integer values inductively defined by $\binom{a}{b}=1$ for $b=0$ and $b=a$ and, between those extremes, $\binom{a}{b}=\binom{a-1}{b-1}+\binom{a-1}{b}.$

By this definition, The right-hand side is $$\binom{N+1}{n+1}=\binom{N}{n+1}+\binom{N}{n} $$Continue to unwind the first summand by the definition $$ =\binom{N-1}{n+1}+\binom{N-1}{n}+\binom{N}{n} $$ $$ =\binom{N-2}{n+1}+\binom{N-2}{n}+\binom{N-1}{n}+\binom{N}{n} =\cdots $$ When fully unwound one has, as desired, $$\sum_{j=n}^N \binom{j}{n}.$$

Some might prefer to say "by inductive hypothesis, the first summand is $\binom{N}{n+1}=\sum_{j=n}^{N-1} \binom{j}{n}$ etc. I don't think it is that different.

For counting we might want to overload and say that we use $\binom{a}{b}$ to denote the cardinality of the collection of $b$ element subsets of $[a]=\{1,2,\cdots,a\}.$ We note for future use that (by an easy bijection) this is also the cardinality of a portion of the collection of the subsets counted by $\binom{a+1}{b+1},$ those which have $a+1$ as a member (the largest.) To show that the values are the same we might note the boundary values are $1$ as needed and $\binom{a}{b}=\binom{a-1}{b-1}+\binom{a-1}{b}$ breaks down the subsets counted by $\binom{a}{b}$ according as $a$ is or is not (the largest) member. Then the completely unwound sum is, as noted, The things counted by $\binom{N+1}{n+1}$ counted according to largest element. More formally, Collection counted has a certain partition and the size of the whole is the sum of the sizes of the parts.

An alternate attack (arguably) leads to the same bijection. The proof above could be describes as by induction on $N \geq n$ where $n$ is arbitrary but fixed.

Instead one could look at it as being by induction on $N$ and for each $N$, all $n \leq N.$ I'll leave the base cases unspecified but the induction step would rewrite

$$\binom{N}{n+1}=\sum_{k=n-1}^{N-1}\binom{k}n$$

$$\binom{N}{n}=\sum_{k=n-1}^{N-1}\binom{k}{n-1}$$ as

$$\binom{N}{n+1}=\sum_{j=n}^{N}\binom{j-1}n$$

$$\binom{N}{n}=\sum_{j=n}^{N}\binom{j-1}{n-1}$$

and then add corresponding pairs of terms to get

$$\binom{N+1}{n+1}=\sum_{j=n}^N\binom{j}n.$$

Note the convenient use of $\binom{n-1}{n}=0$ to make things line up.

If each of the binomial coefficients is the size of a collection of subsets in the usual manner then "adding corresponding pairs of terms" corresponds to "take the union of corresponding collections of subsets" which are then , by familiar bijection, what we want them to be.