Fall 2011 Strategic Practice 1: Section 2 (Story Proofs) - Question 7
Show that for all positive integers n and k with $n\geq k$, $\binom{n}{k} + \binom{n}{k-1} + \binom{n+1}{k}$ doing this in two ways: (a) algebraically and (b) with a "story", giving an interpretation for why both sides count the same thing.
Solution: (a) For the algebraic proof, start with the definition of the binomial coefficients in the left-hand side, and do some algebraic manipulation to yield the result (see iTunes link for full solution). (b) For the "story" method (which proves that the two sides are equal by giving an interpretation where they both count the same thing in two different ways), consider n + 1 people, with one of them pre-designated as "president". The right-hand side is the number of ways to choose k out of these n + 1 people, with order not mattering. The left-hand side counts the same thing in a different way, by considering two cases: the president is or is not in the chosen group. The number of groups of size k which include the president is n C k-1, since once we fix the president as a member of the group, we only need to choose another k - 1 members out of the remaining n people. Similarly, there are nCk groups of size k that do not include the president. Thus, the two sides of the equation are equal.
"Mathematics is the logic of certainty, but statistics is the logic of uncertainty."