## Saturday, January 19, 2013

### 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.