Theorem 6: the Binomial Theorem

Have you ever noticed a similarity between the first few powers of 11 and the first few rows of Pascal‘s triangle?  I’ll write them out, so that you can compare them.  Here are the first few powers of 11.

11^0 = 1

11^1 = 11

11^2 = 121

11^3 = 1331

11^4 = 14641.

And here are the first few rows of Pascal’s triangle.

    1

   1 1

  1 2 1

 1 3 3 1

1 4 6 4 1

Notice anything interesting?  I’d like to explore the link in this post.

Perhaps the first thing is to see whether the pattern continues.  The next row of Pascal’s triangle is

1   5   10   10   5   1,

and 11^5 is 161051.  So something seems to go wrong.  Let’s try to understand this, because there does seem to be something curious going on here.  It would be great if we could understand both why the first few rows are the same, and why the sixth rows are different.

Understanding the links

How do you calculate the powers of 11?  Here’s how I found 11^4, having found that 11^3 is 1331.  I want to multiply 1331 by 11.  That’s the same as multiplying 1331 by 10 (which is easy), and then adding 1331.  (If you do it using long multiplication, that’s exactly what you’re doing.)  So I want to add 13310 and 1331.

   13310

+   1331

   14641

I’m adding 1331 to “1331 shifted one place to the left with a 0 after it”.  So a digit in the answer is the sum of two adjacent digits in 1331 (where we can imagine a 0 before and after 1331: 013310).  But that’s exactly how Pascal’s triangle is generated: each digit is the sum of the two adjacent digits above it!

That appears to explain the link, but why does the connection break down when we get to the sixth row?  Let’s see what the calculation of 11^5 looks like.  We know that 11^4 is 14641, so we want to add 10 times that (146410) to 14641.

   146410

+   14641

   161051

Ah.  So the problem occurs because of “carrying”: 4 + 6 becomes “0 carry 1”, rather than 10.  So there’s a sense in which it feels as though the pattern would continue, if it weren’t for this pesky business of place value!

What next?  I’d like to show you how this relates to something a bit more general.

A more general result

When we looked at powers of 11, we decomposed 11 as 10 + 1, and that helped us to understand what was going on.  I’d like to think now about powers of the more general expression x + y.  Let’s write out the first few powers.  (I’m going to skip the intermediate calculations that I might have used to get these — you might like to do the calculations to convince yourself.)

(x+y)^0 = 1

(x+y)^1 = x+y

(x+y)^2 = x^2 + 2xy + y^2

(x+y)^3 = x^3 + 3x^2 y + 3x y^2 + y^3

(x+y)^4 = x^4 + 4x^3 y + 6x^2 y^2 + 4x y^3 + y^4.

Notice anything about the numbers appearing here?  (They’re called the coefficients.  For example, the coefficient of xy in x^2 + 2xy + y^2 is 2, and the coefficient of x^2 is 1.)  They’re exactly our old friends from Pascal’s triangle again!

Can we explain this?  The good news is that it’s just the same sort of idea as last time.  Let’s think about finding (x+y)^4, once we know that (x+y)^3 = x^3 + 3x^2 y + 3x y^2 + y^3.  We need to multiply (x+y)^3 by x+y.  That is, we need to multiply (x+y)^3 by x, and add it to (x+y)^3 multiplied by y.  It’s perhaps not quite as obvious how to write it out this time, but I’ll have a go.

(x+y)^3 \times x = (x^3 + 3x^2 y + 3x y^2 + y^3)x = x^4 + 3x^3 y + 3x^2 y^2 + x y^3

(x+y)^3 \times y = (x^3 + 3x^2 y + 3x y^2 + y^3)y = x^3 y + 3x^2 y^2 + 3x y^3 + y^4.

Now we need to add these.  I’ll try to align them helpfully to make that easier (although I’ve struggled to get LaTeX to cooperate, so it’s not as pretty as I’d like!).

   x^4 + 3x^3 y + 3x^2 y^2 + xy^3

\underline{+\ \ \ \ \ \ \ \ \ x^3 y + 3x^2 y^2 + 3x y^3 + y^4}

   x^4 + 4x^3 y + 6x^2 y^2 + 4xy^3 + y^4

It’s just the same idea as before: adding pairs of adjacent coefficients!

Let me tell you what the binomial theorem says (since Major-General Stanley, however modern, will not).

Theorem (the binomial theorem) For any real numbers x and y, and any non-negative whole number n, the coefficients of the various terms in (x+y)^n are the numbers of the (n+1)^{\textrm{th}} row of Pascal’s triangle.  More precisely, the terms are of the form \binom{n}{r} x^r y^{n-r}, where r is a whole number between 0 and n (inclusive), and \binom{n}{r} is the (r+1)^{\textrm{th}} entry in the (n+1)^{\textrm{th}} row of Pascal’s triangle.

The numbers \binom{n}{r} have a special name: they are called the binomial coefficients!  They have many interesting properties.  For example, \binom{n}{r} is the number of ways to choose r objects from a collection of n objects (where the order of the r objects doesn’t matter).  In how many ways can you choose three of the seven dwarfs?  Picking Sleepy, Happy and Sneezy is the same as picking Happy, Sneezy and Sleepy: that’s what I mean when I say that the order doesn’t matter.  The answer is that there are \binom {7}{3} = 35 ways.  This is why \binom{n}{r} is read as “n choose r“.

I could say lots more about the binomial coefficients and their interesting properties (including a formula that means that one doesn’t have to write out Pascal’s triangle each time!), but that would make this post too long, so I’ll resist temptation and give some suggestions for further reading instead.

It turns out that there’s a very nice justification of the binomial theorem using the property that \binom{n}{r} is the number of ways to choose r objects from n (where order is unimportant).  I’ll let you think about what that justification is, but here’s a (quite large) hint.  Think about (x+y)^n as (x+y)(x+y)\dotsm (x+y), with n bracketed factors.  Each term in the answer involves an x or a y from each bracket.  How many times will you get x^n?  What about x^r y^{n-r}?

It turns out that it’s possible to give a more general version of the binomial theorem (sometimes attributed to Newton), in which the exponent n doesn’t have to be a non-negative integer.  Although this version is both useful and interesting, I shan’t go into it here.

Why have I chosen to write about the binomial theorem?  The theorem itself is jolly useful: I can tell you what the coefficient of x^{51} y^{49} is in the expansion of (x+y)^{100}, without having to multiply out the whole thing.  But for me perhaps even more interesting are the links with Pascal’s triangle and numbers of combinations, and the various properties of the binomial coefficients.

Further reading

Wikipedia has a fairly extensive discussion of the binomial theorem, including other proofs and the more general version I mentioned above.  It also has quite a lot about Pascal’s triangle.

Advertisements

3 Responses to “Theorem 6: the Binomial Theorem”

  1. Theorem 14: Fermat’s Little Theorem « Theorem of the week Says:

    […] allowed to suppose that , and we want to deduce that .  We can expand , using the binomial theorem.  We get , together with a bunch of terms of the form , with .  It turns out that if then the […]

  2. Theorem 25: Erdős’s lower bound for the Ramsey numbers « Theorem of the week Says:

    […] those vertices.  So the number of s is the number of ways to choose vertices from , which is the binomial coefficient […]

  3. Theorem 37: Sperner’s lemma « Theorem of the week Says:

    […] now on, to avoid writing two cases, but this is really a technical detail.)  Here is the usual binomial coefficient, so just means the size of the middle […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: