Lesson 4

Another example: \[\sum_{k=l}^{n}\binom{n}{k}\binom{k}{l}=2^{n-l}\binom{n}{l}\ .\] On the left is written the number of ways to select (from \(n\) elements, as usual) a subset of size at least \(l\), and then distinguish an \(l\)-element subset inside it. On the right is written the same thing: you can first select the distinguished \(l\)-element subset, and then each of the remaining \(n-l\) elements is either taken or not.