More fun with Pascal's triangle (Challenge #9)

Remember Pascal’s triangle?

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

It’s chock-full of amazing patterns (big surprise). I think I’ll spend a post or two (or three?) looking at a few of them.

First up: as noted by Steve Gilberg, adding up the numbers in each row reveals an interesting pattern: 1 = 1; 1+1 = 2; 1+2+1 = 4; 1+3+3+1 = 8; 1+4+6+4+1 = 16… amazing! The entries in each row add up to successive powers of two!

As a side note, let me tell you a story. Consider the polynomial function

\displaystyle f(x) = \frac{1}{60} x^5 - \frac{5}{24} x^4 + \frac{7}{6}  x^3 - \frac{67}{24} x^2  + \frac{229}{60} x - 1

Go substitute all the values from 1 to 6 into it for x, and tell me what you find. Things aren’t always what they seem.

OK, sorry, that wasn’t really a story, so sue me. Getting back to Pascal’s triangle, it *ahem* appears that the entries in each row add up to successive powers of two. At least, they do for the first eight or nine rows. But do they always? Simply observing this apparent pattern is a great start but it’s not enough.

Another way of expressing the pattern we’ve noticed, in terms of binomial coefficients: it seems that
\displaystyle \sum_{k=0}^n \binom{n}{k} = 2^n

for all integers n \geq 0. (Here’s an explanation of sigma notation if you don’t know what the \Sigma means.)

I won’t keep you in suspense; it turns out that this is true. But can you figure out why? Post your explanations here! I know of at least two, one having to do with the way Pascal’s triangle is defined (in terms of the addition-rule), and one having to do with the way binomial coefficients are defined. But there are probably more.

About these ads
This entry was posted in challenges, pascal's triangle, pattern, proof. Bookmark the permalink.

25 Responses to More fun with Pascal's triangle (Challenge #9)

  1. Pseudonym says:

    Well, the binomial coefficient proof is easy: Simply expand (1+1)^n, and you’ve got it. Incidentally, you can also use this to prove a bunch of other cool factoids. Try expanding 0 = (1-1)^n for starters.
    But that’s not the coolest factoid, IMO. What can you prove about this sequence of numbers?

    \displaystyle C_n = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}{k}

  2. Brent says:

    True, although that assumes you already know the binomial theorem. (I am thinking of writing a post on it soon.) There’s also a more intuitive way to explain it by appealing to the combinatorial meaning of binomial coefficients.

    I took the liberty of surrounding your formula with [ tex ] and [ /tex ] (without the spaces) — anything in between those tags is interpreted as LaTeX, so no need to worry about HTML. At any rate, those factoids are indeed cool. Perhaps some other readers will take you up on your challenge!

  3. Jester says:

    I have one question for the side-note polynomial:
    The values from 1 to 5 seem to work properly (very nice, trying to figure out a proof) but for 6 the result seems to be 33

    Could you double check it too ?

  4. Brent says:

    That’s exactly right! Things aren’t always what they seem. =)

  5. Jester says:

    How did you get to that polynomial? Is it interpolation or something?

    I am a novice in the fields of mathematics (working hard my way up though), so excuse any “silly questions” of mine :)

  6. Brent says:

    No such thing as a silly question! (Well, I suppose that’s not technically true, but you know what I mean. =) How I got to that polynomial is probably deserving of a couple posts in and of itself, but I’ll see if I can sketch the method quickly. In general it is always possible to find a degree-n polynomial which will pass through any (n+1) points of your choosing (as long as no two points have the same x-coordinate). Say your polynomial is

    f(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0.

    Then saying you want it to pass through the point (u,v) is the same as saying you want the equation f(u) = v to be true. Creating an equation out of each of your chosen points in this way gives you a system of n+1 linear equations (one for each of your points) with n+1 unknowns (a_n through a_0). You can then solve this system of equations to find the coefficients of the desired polynomial (in my case I had a computer do it for me, using matrices).

    That’s probably long enough for one comment, but if you want more details than that, just let me know!

  7. Jester says:

    Ok, thanks very much. I think i got the point !

  8. Jester says:

    Sorry for the double post, but another question just popped.

    Your degree-5 polynomial should pass from 5+1 given points. So f(6)=33 i suppose was your choice ?

  9. Brent says:

    That’s right. I suppose I could have just made a degree-4 polynomial to pass through f(1)=1 to f(5)=16 and left f(6) up to chance (it probably would not be 32) but somehow I thought it would be more fun to have f(6) be so close to continuing the pattern… but not quite!

  10. Jester says:

    Allright now, all things explained :-D

    You are a very get-other-people-scratch-their-heads person though! That rocks !!

  11. Brent says:

    Thanks! =)

  12. tang says:

    Hmm…

    Why not just simple mathematical induction? Let (n, x) be the row and column of a number in Pascal’s triangle (starting with row 0 and column 0). For example, (4, 2) = 6.

    There are two ways to define Pascal’s triangle I think.

    1. Let (0, 0) = 1 and (0, x) = 0 for any x not equal to 0. Then define recursively, (n, x) = (n-1, x-1) + (n-1, x) for n > 0.

    With this definition, it turns out that the the sum of the elements of any row is equal to twice the sum of the elements in the previous row. And since row 0 summed to 1, row 1 will sum to 2, row 2 will sum to 4, etc, all powers of 2.

    2. Define (n, x) = nCx. So the triangle becomes

    0C0
    1C0 1C1
    2C0 2C1 2C2
    3C0 3C1 3C2 3C3
    …etc…

    Then once can prove the combinatorial identity that

    nCx = (n-1)C(x-1) + (n-1)Cx

    And then the argument follows in the same way as the previous way to define Pascal’s triangle.

    -I hope I didn’t make any mistakes

  13. Brent says:

    Yup, that definitely works! No mistakes that I can see.

    There’s still (at least) one more way (that I know of) to explain it…

  14. Jonathan says:

    I’ve got to stop by here more often (and I will, just added you to my links)

    So I have a fun way, without reference to “that triangle”

    Consider a set of n objects. How many subsets does it have? I have two solutions.

    1. Consider the subsets of each different size (cardinality). There are C(n,n) (which is one) subset of order n, C(n,n-1) subsets of order n – 1, and so one, down to C(n,1) = n subsets of order 1 and of course C(n,0) 1 subset with nothing in it!

    2. Lets count the subsets differently. Look at each element of the original set, and say “yes” we will include it, or “no” we will not. That’s 2 choices for the first element, 2 for the second, 2 for… Actually, it’s 2 choices for each. They are independent, so we multiply, and get 2^n

    Since the left and right hand sides of your equation answer the same question, they must be equal.

  15. Brent says:

    @Jonathan: yup, that’s the other way I had in mind! =) Pretty nifty.

    I’d be honored to have you stop by more often, I just added your blog to my reading list as well.

  16. Nick Perry says:

    Hey Brent :)

    This is way outside the purview of this particular post, but I thought I’d share my favorite Pascal property. The proof follows from the way in which the triangle is constructed and a combinatorial argument.

    Pascal’s triangle describes the number of vertices, edges, faces, etc. of any n-dimensional triangle (a simplex, if you want to get technical about it).

    Check out the 1-3-3-1 row. Disregard the first 1, so that you have 3-3-1.
    How many vertices (zero-dimensional corners) are in a two-dimensional standard triangle? 3.
    How many edges (one-dimensional sides) are in a triangle? 3.
    How many faces (two-dimensional areas) are in a triangle? 1 — the triangle itself.

    Next, check out the 1-4-6-4-1. Again, disregard the initial 1, so that you have 4-6-4-1.
    How many vertices are in a three-dimensional triangle (aka tetrahedron, aka triangular pyramid)? 4.
    How many edges are there in a tetrahedron? 6.
    How many faces? 4.
    How many spaces (three-dimensional volumes)? 1.

    This generalizes up and down through all dimensions, though it obviously gets tricker to visualize. You can modify the rules of generating Pascal’s triangle so that it will do the same trick for n-dimensional squares, also.

  17. Brent says:

    Hey there Nick!

    That’s pretty nifty — it makes sense to me why it’s true, but I’d never thought of interpreting Pascal’s triangle in that way before.

  18. linda says:

    Is there any way to simply explain what this pattern is for and why one would use it? If all it is, is just counting, why would you use this? Thanks.

  19. Brent says:

    Hi linda,

    Well, if you want an idea of how it is connected to the “real world”, you could note that binomial coefficients (the entries in Pascal’s triangle) tell you how many ways there are to choose k things out of n total things; then, the fact that each row sums to 2^n means that there are 2^n ways to choose as many (or as few) things as you want out of n things. For example, if an ice cream store has chocolate, vanilla, and strawberry, then you have 2^3 = 8 different choices (including not getting any ice cream, getting only strawberry, getting chocolate and vanilla, etc.).

    But as for “what the pattern is for”, I’m not sure that’s the right question to ask. The pattern just is — if you write down a triangle of numbers where each one is the sum of the two above, and add up the rows, you get powers of two. The pattern exists because that’s the way the universe is structured, not because it is useful. =) Although it is pretty nifty that it happens to also correspond to a “real-world” interpretation.

  20. Cody says:

    What does the 27th row of pascal’s triangle look like?

  21. Brent says:

    Cody: why, it looks like a bunch of numbers, of course. =) If you’d like to see how to calculate the entries of the 27th row of Pascal’s Triangle, try reading these previous posts:

    http://www.mathlesstraveled.com/?p=52

    http://www.mathlesstraveled.com/?p=55

  22. Pingback: Challenge #9 Solution « The Math Less Traveled

  23. antonio says:

    why do the rows in pascal’s triangle add up to powers of 2? is there a math explanation for this ?

  24. Brent says:

    antonio: yes, there is. See the next post (and subsequent ones) for an explanation.

  25. Claudine says:

    Can you explain it please…..Make it more clear because our project in math is to prove pascal triangle.I don’t understand other’s post.please make it clear.sorry.thanks for your site…

Comments are closed.