The Christmas Stocking Theorem is so named because if we
draw Pascal's Triangle the usual way as an array shaped liked an isosceles
triangle, we sum down any diagonal, either left or right, the total will
be the entry one row down and one diagonal over, so it looks like a long
boot or sock. This was the second identity Pascal proved, and he wrote
the array as a rectangular array as follows:
What we think of as the rows of Pascal's Triangle now
appear as diagonals, which we have marked with / lines between the rows
of this array; examples of the Christmas Stocking now work as follows,
show in color in the array below.
As we see in this formation, we add the numbers along
a row and the sum is equal to the number below the last number we used in
the row sum, or we add all the number along a column and the sum is the number
to the right of the last number used in the column sum. Since this
is a symmetric matrix, which means rowk and columnk
are transposes of one another, if we prove it works across a row, the proof
also works down a column. We are going to use induction on the number
of entries in the sum. We are going to call all the numbers in the
sum before the last number the leg, the last number in the
sum the heel, and the target number in the row below the
toe. Our induction is going to be done on the length of the
leg.
Step 1: Leg length = 0 This part is easy, because this means both the heel = 1 and
the toe = 1, since with no leg, the entries for the
toe and the heel are in the first row, which is all 1's. Sometimes
the first step of an induction proof is so obvious, you feel like you should
look at the next case, which would mean leg length = 1; here, in rowk,
we would get 1+k = k+1; this is also pretty obvious, but at least we see
the pattern working early.
Step 2: Assume legn+heeln=
toen. We need to provelegn+1+heeln+1=
toen+1
Here we will use symbols instead of numbers to show the relationship
between one Christmas Stocking and the next.
Because we can replace the new, longer leg with the toe of the
previous stocking, this means we only need to prove #+?=!; if we look back at this way of writing
Pascal's Triangle, we see that this pattern is simply the Basic Additive
Identity, Cat. # 1100001.
While we like the Christmas Stocking as a name for this theorem,
readers of Concrete Mathematics will know these ideas as upper summation
and parallel summation.
Note: According to Russ Merris, this theorem was first called
The Christmas Stocking by the late Ken Rebman of California State University,
Hayward, who gave the author his first exposure to both linear algebra
and combinatorics.
