Math 239

Proving Combinatoric Identities

1. Define a set

2. Count the set in 2 different ways:

   1. One way that shows the left side

   2. One way that shows the right side

3. For summations of products (e.g. $\sum\limits_{k=0}^n {n \choose k}^2$), think of how to split each subset into groups.

Reminders for Understanding

• Weights represent element in set => coefficients represent number of elements that appear