-2
$\begingroup$

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?

$\endgroup$
7
  • 8
    $\begingroup$ Split into cases based on the largest element of a subset of $[N+1]$ of size $[n+1]$. $\endgroup$ Commented Dec 25, 2017 at 22:28
  • 16
    $\begingroup$ You have $N+1$ reindeer and need to choose $n+1$ for your sleigh. They are ordered by redness of nose. You can choose one reindeer to lead the sleigh, call it the $(j+1)$th reindeer, then $n$ additional less-red-nosed reindeer to complete your team. $\endgroup$ Commented Dec 25, 2017 at 22:32
  • 1
    $\begingroup$ Probably the real gist of the question is the definition of "purely bijective proof". I'm wondering why the OP thinks the usual proof is not "purely bijective". $\endgroup$
    – Fan Zheng
    Commented Dec 26, 2017 at 2:49
  • $\begingroup$ @FanZheng Please enlighten me on what "the usual proof" is? The one that first leapt into my mind was an induction proof (induction on $N-n,$ wherein the identity follows from Pascal's triangle). $\endgroup$
    – Igor Rivin
    Commented Dec 26, 2017 at 3:42
  • $\begingroup$ @IgorRivin I'm just curious what do you think about the proofs given in the two comments above (which is what I call "the usual proof"). $\endgroup$
    – Fan Zheng
    Commented Dec 26, 2017 at 16:56

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .