In Which Our Hero (You) Discovers Several Methods of Proving a Combinatorial Identity Involving Pascal’s Triangle
(Read Challenge #9 first if you haven’t already…)
- Because of the way Pascal’s triangle is defined, each entry “contributes” to the entries below, and below to the right. Since each entry contributes to two other entries, it follows that the sum of all the entries in each row will always be twice the sum of the entries in the previous row. The sum of the entries in the first row is obviously 1, so the subsequent row sums will be 2, 4, 8, 16… powers of two.
- Since the binomial coefficient tells us the number of ways to pick exactly k things out of n, the sum of all the binomial coefficients from to tells us the total number of ways to pick any number of things out of n. That is, someone shows you n things, and says you can take as many or as few as you want (including all, or none). How many choices do you have? You have two choices for each individual item: you can either take it, or not. So the total number of choices is .
Next time I’ll talk more about the enigmatic method of proof suggested by Anonymous*: “Simply expand (1+1)^n, and you’ve got it.” This refers to the Binomial Theorem, an important generalization of what we’ve been talking about — so important, in fact, that it’s where binomial coefficients get their name. Fortunately for us, it’s also totally sweet.
(*Name changed to protect identity)