## Sunday, January 20, 2013

### The Hockey Stick Theorem

Earlier, we discussed the pattern from Pascal's Triangle known as the Christmas Stocking Theorem, named for a shape that has a toe and a leg, the leg being a column inside the triangle. Here is an example in bold and blue.

1
1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5 10 10 5  1
1  6 15 20 15  6  1

What this shows is that 20 = 10+6+3+1, the toe of the stocking equal to the sum of the numbers in the leg.

A Hockey Stick will lie flat across a row like this

1
1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5 10 10  5  1
1  6 15 20 15  6  1
1  7 21 35 35 21  7  1

Obviously, the 6 in the toe is not the sum of the numbers in the row below. It is the alternating sum, which is to say we start at the 21 just below the 6, then subtract the 35 to the left, then add the next 35, subtract the next 21, add the 7 then subtract the 1. Let me write it this way, with the subtractions written in red.

6 = 21 - 35 + 35 - 21 + 7 - 1

Here is the summation notation of the pattern.

If I were in front of a class, I would say

"n choose r equals the alternating sum of negative one to the r-k power times n+1 choose k as k goes from 0 to r."

Alternating sums always have -1 raised to integer powers, since (-1)(-1) = 1 but (-1)(-1)(-1) = -1, etc. -1 raised to an even power is 1, while raised to an odd power is -1.

Tomorrow, we will learn the closed form of the binomial coefficients, a useful thing to know if we want to find out the different number of five card hands in poker without having to write out rows 0 to 52 of the triangle.