There are lots of combinatorial identities. It is not necessary to remember them all. Remembering a handful of them is sufficient to tackle most of competition problems. Though many identities can be proved by directly applying combination number definition, it is extremely helpful to be able to explain their functional meaning and, sometimes, prove them in a counting way.

For example, the following relation is one of the most basic combinatorial identities: $$C_n^k = C_n^{n-k}$$

While it can be easily proved by applying the combination number definition as following (the applying-the-formula method) $$C_n^{n-k}=\frac{n\times(n-1)\times\cdots(n-(n-k)+1)}{1\times 2\times\cdots(n-k)}=\frac{n\times(n-1)\times\cdots(n-k+1)}{1\times 2\times\cdots\times k}=C_n^k$$

this identity can also be explained by noting that selecting some people from a group is the same as not selecting the remaining people who are not selected. This means that "selecting $k$ out of $n$ people is equivalent to selecting $(n-k)$ out of $n$ people".

The additive identity $${n \choose k } + {n \choose k+1}={n+1 \choose k+1}$$ provides another example. While this identity can be easily proved using the applying-the-formula method, it can also be easily explained using the Pascal triangle as shown in the video tutorial. One benefit of using the Pascal triangle method is to help remember such identity in an easier way.

Similar to the additive identity, the famous Hockey-stick Identity can also be explained and remembered using the Pascal triangle.

There are several other not-to-apply-the-formula methods. We will discuss them in the next few lessons.

Note: this video tutorial covers many other lessons in addition to this one because it is logical to group them together and discuss at once. But lesson contents, description, examples and assignments will be given separately.

A list of commonly used combinatorial identities can be found here. They need to be remembered.