The 'Counting the same thing two ways' approach that Erin Schram mentioned in my old blog (for those that remember it!) is enormously powerful. It can be used to prove all sorts of combinatorial relationships with simple counting arguments rather than algebra. Here are a couple very simple examples:

\binom{n-1}{r-1} + \binom{n-1}{r} = \binom{n}{r}

We can pound away with algebra and prove this, or we can use a simple counting argument. The expression on the right is the number of ways to choose a committee with r people from a group of n people. On the left, we consider this committee selection from the point of view of one of the people, say Bob. There are

\binom{n-1}{r-1}

ways to form the committee by including Bob and

\binom{n}{r-1}

ways to form the committee without Bob. Either the committee has Bob or it doesn't, so our desired relationship follows.

The committee-forming model is one of the most commonly used models for combinatorial arguments. Another is the block-walking model, in which we count the number of ways we can walk down Pascal's Triangle by taking a series of down-left or down-right steps. Clearly there are

\binom{n}{r}

ways to get to the point denoted by

\binom{n}{r}

in Pascal's Triangle, since we must take n steps to get there, of which r of them are to the right (or left).

A counter's view of Pascal's Triangle is:





We can quickly prove the above identity by noting that the left-hand side represents the sum of the numbers of ways to get to the two points just above

\binom{n}{r}

.

Here's another example:

\displaystyle\binom{n}{0} + \binom{n}{1} + \cdots +\binom{n}{n} = 2^n

Committee-forming: To form a committee from n people, we can make it with 0 people, with 1 person, with 2 people, etc., giving the sum on the left. Alternately, we can note that each person has 2 choices - be on the committee or not be on the committee, so there are

2^n

ways to form the committee. Hence, we have the desired relationship.

Block-walking: There are

2^n

ways to take n steps. The left side gives us the total number of ways to walk down to the n-th row by counting the number of ways we can get to each point on the n-th row.

Here are a few more examples to play with on your own:

Show that

\displaystyle\binom{r}{r} + \binom{r+1}{r} + \binom{r+2}{r} +\cdots+\binom{n}{r} = \binom{n+1}{r+1}

Show that

\displaystyle\sum_{i=0}^k\binom{n}{r}\binom{m}{k-r} = \binom{m+n}{k}

Show that

1(1!) + 2(2! ) + 3(3!) + \cdots + n(n!) = (n+1)! - 1

Perhaps later I'll get around to writing up a combinatorial approach to Fibonacci identities.