An informal proof of the Christmas Stocking Theorem

Let's put a few rows of Pascal's triangle up yet again and choose one of the entries "at random", providing it isn't in the leftmost column.

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
1  8 28 56 70 56 28  8  1

The first rule we have learned about entries in that any entry is the sum of the entry just above it and the entry above it and to the left, in this case, 35+21 = 56.


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
1  8 28 56 70 56 28  8  1

I'm going to use the same rule on the 21, changing it to 15+6, the entries above it.

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
1  8 28 56 70 56 28  8  1

Now the 6,  changing it to 5+1, the entries above it.

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
1  8 28 56 70 56 28  8  1

Now the 1 in row 5 is exchanged for the 1 in row 4, actually 1 = 1+0, but the zero is invisible.

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
1  8 28 56 70 56 28  8  1

Now I un-bold the 1 in row 5 and we have our standard Christmas Stocking, the sum of the leg in bold red being equal to the toe in bold black.


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
1  8 28 56 70 56 28  8  1

Here is how I could say the theorem in everyday language.

Pick any column in Pascal's Triangle.  Starting at the top of the column, select as many entries as you want and add them up. The sum will be equal to the entry that is one row down and one column to the right of the position where you list of entries ended.

Here is how I would write this in summation notation.  The letter k stands for the column, the letter n stands for where we stop counting and the letter j is the summation variable, which goes from k to n.

Here is how I would say this summation out loud if I were explaining it in class.

The sum as j goes from k to n of "j choose k" is "n+1 choose k+1".

The parentheses with two numbers on top of each other is the standard way to write the numbers of Pascal's Triangle, known collectively as the binomial coefficients. The editor that Blogger uses doesn't have an elegant way to put up a summation symbol or stacking numbers inside a parentheses, so I will write "8 choose 5" = 56 when I mention an entry or "j choose k" when discussing a general entry.

Tomorrow: Why the entries are called binomial coefficients.