How do I prove this combinatorial identity using inclusion and exclusion principle?

Solution 1:

Expanded from Pedro Sánchez Terraf's answer, but added my view to write a more combinatorial proof.

Viewing the diagonals of the Pascal's triangle, recall that $\binom {m+n-1} m$ represents the $n$'th $m$-dimensional simplex number. (Ones for $0$-dimension, natural numbers for $1$-dimension, then triangle numbers, tetrahedral numbers, pentatope numbers, etc.) (e.g. $\binom {n+1} 2$ represents the $n$'th triangle number)

With fixed $m$ and $n$, let $A_i$ be the set of integers from $1$ to $\binom {(m-1)+i-1}{m-1}$, $i = 1 \ldots (n-m+1)$: $$\begin{align*} A_1 &= \left\{1, \ldots, \binom {m-1}{m-1}\right\} = \left\{1\right\}\\ A_2 &= \left\{1, 2, \ldots, \binom{m}{m-1}\right\}\\ &= \left\{1, 2, \ldots,\binom m1\right\}\\ &= \left\{1, 2, \ldots, m\right\}\\ &\vdots\\ A_i &= \left\{1, 2, \ldots, \binom{m+i-2}{m-1}\right\}\\ &\vdots\\ A_{n-m+1} &= \left\{1, 2, \ldots, \binom{(m-1)+(n-m+1)-1}{m-1}\right\}\\ &= \left\{1, 2, \ldots, \binom {n-1}{m-1}\right\}\\\\ \end{align*}$$ Call the number of sets, and also the number of terms, $n-m+1$, be $N$.

Edit added: In hindsight, $A_{n-m+1}$'s may as well be sets of balls that form the $(n-m+1)$th simplex in $m$ dimension. All the other $A_i$'s are the set of balls that form smaller $m$-simplexes of size $i$, are subset of $A_{n-m+1}$, and share the same vertex.

For the right hand side, the union of all these sets is $$\left|\bigcup_{i=1}^{N}A_i\right| = \left|A_{N}\right| = \binom {n-1}{m-1}$$

For the left hand side, the first term, $$\begin{align*} \sum_{i=1}^{N} \left|A_i\right| =& \sum_{i=1}^{N} \binom{m+i-2}{m-1} \\ =& \sum_{i=1}^{N} \binom{(m-1)+i-1}{m-1}\\ =& \binom{m + N -1}{m}\\ =& \binom{n}{m} \end{align*}$$ The second-to-last step comes from the definition that, the sum of the $1$st to the $N$'th simplex number is the $N$'th simplex number of the next dimension.

For each of the later term, say the $k$'th, out of the $N$ sets, each time $k$ of the sets have their set intersection taken and added. ($1 \le k \le N = n-m+1$)

There are $\binom{N-1}{k-1}$ sets that contain $A_1$, and the size of each of those intersections will be $1 = \binom{m-1}{m-1}$. Then there are $\binom{N-2}{k-1}$ sets that contain $A_2$ but not $A_1$, etc. Summing the count of those intersections with their respective sizes, the $k$'th term on the left hand side of OP's formula is $$\begin{align*} \sum_{i=1}^{N-(k-1)}\binom{m+i-2}{m-1}\binom{N-i}{k-1} &= \sum_{i=1}^{N-k+1}\binom{(m-1)+i-1}{m-1}\binom{(k-1)+(N-k+2-i)-1}{k-1} \end{align*}$$ Each of the two binomial coefficients is a sequence of hyper-tetrahedral number. The second binomial coefficient, $\binom{N-i}{k-1}$ runs from $\binom{N-1}{k-1}=\binom{(k-1)+(N-k+1)-1}{k-1}$ back to $\binom{k-1}{k-1} = \binom{(k-1)+1-1}{k-1}$. When viewed as a term-by-term product of two sequences of tetrahedral numbers, the result is another tetrahedral number of higher dimension: $$\binom{n}{m+k-1}$$

See edited below But this is just my intuition and I have yet to fully proved this.

The summation is consistent with the last two terms in OP's formula:

when $k = N-1 = n-m$, the summation consists of two terms, $$\begin{align*}\binom {m-1}{m-1}\binom{N-1}{N-2} + \binom {m}{m-1}\binom{N-2}{N-2} & =(N-1)+m\\ &= n \\ &=\binom{n}{n-1} \end{align*}$$ which confirms that are $N-1=n-m$ intersections each with $1$ element, and $A_2\cap A_3 \cap \cdots \cap A_N$ which has $m$ elements.

when $k = N = n-m+1$, the summation consists of one term, $$\binom {m-1}{m-1}\binom{N-1}{N-1}=1=\binom{n}{n}$$ which also confirms that the intersection of $A_1, A_2, \ldots, A_{n-m+1}$ has only one element.

Edit: To prove: $$\sum_{i=1}^c\binom {a+i-1}a \binom{b+(c+1-i)-1}b = \binom{(a+b+1)+c-1}{a+b+1}$$ I have added extra parentheses and terms so that each binomial coefficient can be translated directly to a simplex number with specific dimension.

First, the summation introduces 1 dimension. Call this the $x$-direction.

Second, consider $\binom{a+i-1}a$ only. Each term itself is the $i$th simplex number in $a$-dimension. Extend the 1-dimensional world to $1+a$ dimension world, with new orthogonal directions $y_1, y_2, \ldots, y_a$.

Then for each of the $c$ terms, arrange $\binom{a+i-1}a$ balls in the simplex shape in the new $a$ dimensions, in an integer grid of origin $(1,1,1,\ldots, 1)$. The simplex is right-angled with $a+1$ vertices at $(y_1, y_2,y_3, \ldots, y_a) =$ $$(1,1,1,\ldots, 1),\ (i, 1, 1, \ldots, 1),\ (1, i, 1, \ldots, 1),\ (1, 1, i, \ldots, 1),\ldots,\ (1, 1, 1, \ldots, i)$$

Stack the $c$ simplexes along $x$-direction, by putting the $i$th simplex at $x=i$. This stack of sequential simplexes gives an $(a+1)$-simplex of vertices at $(x; y_1, y_2,y_3, \ldots, y_a)=$ $$(c; 1,1,1,\ldots, 1),\ (c;c, 1, 1, \ldots, 1),\ (c;1, c, 1, \ldots, 1),\ (c;1, 1, c, \ldots, 1),\ldots,\ (c;1, 1, 1, \ldots, c)$$ and the origin $(1;1,1,1,\ldots,1)$

Third, again, extend the world from $1+a$ dimensions to $1+a+b$ dimensions, calling the new $b$ orthogonal directions as $z_1, z_2, \ldots, z_b$.

For each ball previously on the $x=i$ slice, the number has to be multiplied by $\binom{b+(c+1-i)-1}b$, which is the $(c+1-i)$th simplex number in $b$ dimension. Arrange $\binom{b+(c+1-i)-1}b$ balls in a $b$-simplex shape with right angle at the origin $(z_1, z_2, \ldots, z_b) = (1, 1, \ldots, 1)$. Copy this simplex for every ball on the $x=i$ slice. Repeat this for every slice on the $x$-direction, and the new simplex is finished, with dimension $a+b+1$.

The new simplex has vertices at $(x; y_1, y_2, \ldots, y_a; z_1, z_2, \ldots, z_b)=$

• The origin: $(1;1,1,\ldots,1;1,1,\ldots,1)$
• To $x$-direction: $(c;1,1,\ldots,1;1,1,\ldots,1)$
• To $y$-direcions: $$(c;c, 1, \ldots, 1;1,1,\ldots,1),\ (c;1, c, \ldots, 1;1,1,\ldots,1),\ldots,\ (c;1, 1, 1, \ldots, c;1,1,\ldots,1)$$
• To $z$-directions: $$(1;1, 1, \ldots, 1;c,1,\ldots,1),\ (1;1, 1, \ldots, 1;1,c,\ldots,1),\ldots,\ (1;1, 1, 1, \ldots, 1;1,1,\ldots,c)$$

Notice that for the $y$-directions, the simplex is sheared, and the vertices are not on the "axes" where all but one coordinates are $1$. However, by shearing along every $y$ directions, it is possible to obtain a scaled standard simplex.

And lastly, the number of balls in the $c$th $(a+b+1)$-simplex is $\binom{(a+b+1)+c-1}{a+b+1}$. Substitute $a= m-1$, $b=k-1$, $c=n-m+1$.

And by balls, I mean hyperspheres.

An example of how balls are stacked, $a=2$, $b=2$, $c=4$, which results in a $5$-simplex. The simplex arrangement is sliced perpendicular to $x$, $y_1$ and $y_2$ directions.

Solution 2:

Let's begin by rewriting the formula with a shift from $n$ and $m$ to $n+1$ and $m+1$, so that the expression to prove is

$${n\choose m} = {n+1\choose m+1}-{n+1\choose m+2}+{n+1\choose m+3}-\cdots+(-1)^{n-m}{n+1\choose n+1}$$

Now picture a class with $n$ students and a teacher. Each term on the right is of the form ${n+1\choose k}$, which counts the number of ways you can choose a group of size $k$ from among the $n+1$ people in the class. Among these groups are some that include the teacher and some that don't. Each group of size $k$ that doesn't include the teacher can be identified with a group of size $k+1$ that does include the teacher.

The expression ${n\choose m}$ can be interpreted as counting the number of ways you can choose a group of size $m$ from among the $n$ students only -- and then, if you like, adding the teacher to get a group of size $m+1$. The inclusion-exclusion is now clear: Start with all the ways you can form a group of size $m+1$, then try to eliminate the overcount, which consists of the all-student groups.

Solution 3:

This is too long for a comment, that's why I'm putting it here.

The first observation is that your formula already implies Pascal's identity. Replacing $m$ by $m+1$ we have $$\binom{n}{m+1}-\binom{n}{m+2}+\cdots+(-1)^{n-m-1}\binom{n}{n}=\binom{n-1}{m}.$$ Adding to the original formula gives (after cancelling) $\binom{n-1}{m}+\binom{n-1}{m-1}=\binom{n}{m}$. So, in some sense, any proof of this identity must include some idea proving Pascal's.

Now there is a way to putting the LHS as an application of Inclusion-Exclusion principle. Take the following sets:

$$ \begin{align} A_1 &:= \left\{1,2,\dots,\textstyle\binom{n-1}{m-1}\right\}\\ A_2 &:= \left\{1,2,\dots,\textstyle\binom{n-2}{m-1}\right\}\\ &\dots \\ A_{n-m+1} &:= \left\{\textstyle\binom{m-1}{m-1}\right\} =\{1\}. \end{align} $$ So we have $A_1\supset A_2 \supset \dots \supset A_{n-m+1}$. If you apply In-Ex to prove that $$ |A_1\cup \dots \cup A_{n-m+1}| = |A_1|=\textstyle\binom{n-1}{m-1}, $$ you may obtain (through extensive use of Pascal's and perhaps also induction) the summation on the LHS of your equation.

Solution 4:

Note: This answer is inspired by the deleted answer of @diracpaul.

We analyze lattice paths generated from $(1,0)$ steps in $x$-direction and $(0,1)$ steps in $y$-direction. The number of paths from $(0,0)$ to $(m,n-m)$ is $\binom{n}{m}$. This is valid since for paths of length $n$ we can select $m$ steps in $x$-direction leaving $n-m$ steps in $y$-direction.

Let's write $\binom{n}{m}$ in the more symmetrical version using multinomial coefficients $\binom{n}{m,n-m}$. Using this notation OPs equation becomes

\begin{align*} \binom{n-1}{m-1,n-m}&=\binom{n}{m,n-m}-\binom{n}{m+1,n-m-1}\\ &\qquad+\binom{n}{m+2,n-m-2}-\cdots+(-1)^{n-m}\binom{n}{n,0}\tag{1} \end{align*}

For convenience only we change the representation by setting $x=m$ and $y=n-m$. Then OPs equation (1) becomes

\begin{align*} \binom{x+y-1}{x-1,y}&=\binom{x+y}{x,y}-\binom{x+y}{x+1,y-1}\\ &\qquad+\binom{x+y}{x+2,y-2}-\cdots+(-1)^{y}\binom{x+y}{x+y,0}\tag{2} \end{align*}

Before we interpret the identity (2) one additional aspect. We can use only $(1,0)$ steps or $(0,1)$ steps. So, when we go from $(0,0)$ to a point $(x,y)$ with $x,y>0$, we have to pass either $(x-1,y)$ or $(x,y-1)$. This gives the well known identity

\begin{align*} \binom{x+y}{x,y}=\binom{x+y-1}{x-1,y}+\binom{x+y-1}{x,y-1}\tag{3} \end{align*}

Now we claim the following:

• The LHS of (2) gives the number of paths of length $x+y-1$ from $(0,0)$ to $(x-1,y)$.

• The RHS of (2) gives the number of paths of length $x+y$ from $(0,0)$ to $(x,y)$ which pass $(x-1,y)$.

Since there is only one possibility to go from $(0,0)$ to $(x,y)$ via $(x-1,y)$, namely by adding a $(1,0)$ step from $(x-1,y)$ to $(x,y)$ it's obvious that both parts give the same number. According to (3) we conclude

\begin{align*} \binom{x+y-1}{x-1,y}&=\binom{x+y}{x,y}-\binom{x+y-1}{x,y-1}\tag{4} \end{align*}

The RHS of expression (4) is correct, but not the same as the RHS of (3).

The idea is to approach the representation (3) step by step. We note that $\binom{x+y-1}{x,y-1}$ is the number of paths of length $x+y-1$ from $(0,0)$ to $(x,y-1)$. We argue now similar as above and say that this is the same as the number of paths of length $x+y$ from $(0,0)$ to $(x+1,y-1)$ passing through $(x,y-1)$.

This is realised according to (3) via

\begin{align*} \binom{x+y-1}{x,y-1}&=\binom{x+y}{x+1,y-1}-\binom{x+y-1}{x+1,y-2}\tag{5} \end{align*}

Combining this with (4) gives

\begin{align*} \binom{x+y-1}{x-1,y}&=\binom{x+y}{x,y}-\binom{x+y-1}{x,y-1}\\ &=\binom{x+y}{x,y}-\binom{x+y}{x+1,y-1}+\binom{x+y-1}{x+1,y-2} \end{align*}

And again we substitute the surplus $\binom{x+y-1}{x+1,y-2}$ by the number of pathes of length $x+y$ from $(0,0)$ to $(x+2,y-2)$ passing through $(x+1,y-2)$. This results in

\begin{align*} \binom{x+y-1}{x-1,y}&=\binom{x+y}{x,y}-\binom{x+y-1}{x,y-1}\\ &=\binom{x+y}{x,y}-\binom{x+y}{x+1,y-1}+\binom{x+y}{x+2,y-2}-\binom{x+y-1}{x+2,y-3} \end{align*}

Proceeding in this way we finally reach step by step the RHS of (2). Observe that the amounts of surplus are compensated according to the inclusion-exclusion principle.

We conclude: The binomial identity

\begin{align*} \binom{x+y-1}{x-1,y}&=\binom{x+y}{x,y}-\binom{x+y}{x+1,y-1}\\ &\qquad+\binom{x+y}{x+2,y-2}-\cdots+(-1)^{y}\binom{x+y}{x+y,0}=\tag{2} \end{align*}

shows that the number of paths of length $x+y-1$ from $(0,0)$ to $(x-1,y)$ is the same as the number of paths of length $x+y$ from $(0,0)$ to $(x,y)$ passing through $(x-1,y)$, whereby the surplus can be compensated by successively adding and subtracting paths of length $x+y$ according to the inclusion-exclusion principle.