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.

The sum of the n-th row of Pascal's Triangle is 2 to the n-th power

Yesterday, we proved the statement that is the title of this post. Why prove it again?

Proof in mathematics is vitally important and multiple proofs of the same fact (or theorem) can show different ways things are connected to each other.

The style of proof we see today is called induction. Here is the basic idea.

1. Make a statement about an infinite number of things that you can put in order.
2. Prove it for the first thing.
3. Prove that if it is true for any given thing on the list, it must also be true for the next thing on the list.

The infinite things we are putting in order are the sums of the rows of Pascal's Triangle.

1=1
2=1+1
4=1+2+1
8=1+3+3+1
...

The first thing on the list is the sum of 1 in row 0. 1 = 2º, so that means we have done steps 1 and 2 of induction.

Now I'm going to cheat a little to make things clear. I am going to use the third row of Pascal's Triangle for my next step. I shouldn't use a specific row because induction has to be about any given row. I'm going to cheat here to convince the reader that what happens to go from the third row to the fourth row happens going from any row to the next.  I'm going to use four different colors on the four different numbers.

1 3 3 1 

next row created by adding numbers from the current row. (0 are in black.)

0+1 1+3 3+3 3+1 1+0

Notice that every color of number shows up exactly twice, two purple 1s, two red 3s, two green 3s and two blue 1s. This means that the sum of this row must be exactly twice the sum of the row we were looking at.

Proving this is true between rows three and four is not enough. You need to convince yourself the pattern of doubling is true between any two consecutive rows. The reason that it's true is that every number in a row is used exactly twice in two different sums to create the entries of the next row.

Tomorrow, we continue to look at patterns in Pascal's Triangle.  We have seen the Christmas Stocking, now we will discover the hockey stick.
 
 

A pattern within the perfect squares.

The perfect squares are the numbers that are the result of multiplying a whole number by itself.

On Tuesday, we saw that every perfect square is the sum of two consecutive triangular numbers, such as 21 + 15 = 36 = 6², illustrated below with 21 black asterisks (6+5+4+3+2+1) and 15 red asterisks (1+2+3+4+5).

* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *

Here is another summation method that gives us the perfect squares, once again illustrated with squares made from asterisks, starting with 1² = 1.

*

2² = 4 = 1 + 3.

* *
* *

3² = 9 = 1 + 3 + 5.


* * *
* * *
* * *


4² = 16 = 1 + 3 + 5 + 7.

* * * *
* * * *
* * * *
* * * *

The most direct way to state this is n² is the sum of the first n odd numbers or n² = 1 + 3 + ...  + (2n - 1).

Taking the sum of a pattern of numbers is very common in math, so we took the capital Greek letter sigma as the symbol for summation.  Blogger software doesn't have an easy way for me to write sigma correctly, so I will add a picture.

The big thing at the front that looks like an M lying on its side is the sigma. I also introduced a new variable k, which is the counting variable. The symbols above and below the sigma mean "k starts at 1, and increases by 1 each time until it gets to n, then we stop". The (2k - 1) shows the things we are adding together.

When k = 1, then 2(1) - 1 = 1.
When k = 2, then 2(2) - 1 = 3.
When k = 3, then 2(3) - 1 = 5.
When k = 4, then 2(4) - 1 = 7.
etc. ...

Tomorrow: a pattern concerning squares and the prime numbers of the form 4k + 1.