Lesson 1

Above we already saw several remarkable properties of binomial coefficients. Many of them are easily proven combinatorially. In such proofs, we show that the left-hand and right-hand sides of the equality represent two ways of calculating the same thing. Such proofs often turn out to be more visual than proofs based on algebraic manipulations with binomial coefficients.

Let’s briefly recall some of the identities we have encountered:

• All subsets:  \(\sum_{k=0}^{n}\binom{n}{k}=2^{n}\).


• Even and odd subsets:  \(\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}=0\) (for \(n>0\)).


• Teams with Alice and without:  \(\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\).


• Teams with the captain:  \(\sum_{k=1}^{n}k\binom nk=n2^{n-1}\).


• Words in a three-letter alphabet:  \(\sum_{k=0}^{n}2^{k}\binom{n}{k}=3^{n}\).