Lesson 2

In the examples above, we relied several times on the method of the distinguished element. One can say that this is a special case of a more general method, where the set is divided into two parts. Here is an example: \[\sum_{k=0}^{n}\binom{n}{k}^{2}=\binom{2n}{n}\ .\] The expression on the right suggests that it represents the number of ways to choose \(n\) elements from a set of size \(2n\). To confirm that the left-hand side represents the same, we divide the set into two parts of size \(n\). Then, to choose a set of size \(n\), we need to select \(k\) elements from the first part, and \((n-k)\) from the second. The number of ways to do this is \[\binom{n}{k}\binom{n}{n-k}=\binom{n}{k}^{2} \ .\]