Binomial Theorem

The Binomial Theorem assures that the sum and product outcome of the following pseudo-code will be equivalent:

sum = 0;
for (int r = 0; r <= n; r++) {
  sum += (n!/((n-r)!r!))(a^(n-r))(b^r);
}

product = (a + b)^n;

where n is a nonnegative integer.  n!/(r!(n-r)!) is the binomial coefficient, pronnounced as "n choose r."

See also:
    binomial coefficient

this was a nodeshell rescue

A law of algebra, showing how to expand the term

(a + b)ⁿ

That is,

(a + b)ⁿ = sum (i=0..n, a^(n-i)bⁱ * n! / ((n-i)!i!) )

when n is a natural number.

For reasons known only to pedants, you will occasionally see high school algebra teachers inflict a different form of the binomial theorem on unsuspecting students.

Sir Isaac Newton was able to generalize the binomial theorem so that it works for any rational n:

(1 + x)ⁿ = 1 + sum [i=1..infinity, xⁱ*prod(j = 0..i-1, n-j) / i!]

where |x| < 1. If we can arrange things so that |a| > |b|, we can formulate (a + b) as a * (1 + b/a) and use the above formula.

(a + b)ⁿ = sum (i = 0..infinity, C(n, i) aⁱb^n-i)

This form leads to an important application in calculus, where an otherwise unintegrable term can be converted into an infinite series and integrated.

---

The binomial theorem was proven by the Arab mathematician al-Karaji sometime in the 10th century.  Chinese mathematicians knew about binomial coefficients by 1261 at the latest.

You should notice two patterns about the integer coefficients:

C (n, i) = n(n-1)(n-2)..(n-i)/i!
         = n!/(i!(n-i)!) when n is an integer.

This is the same formula for the number of posible combinations out of a set of n elements, taking i of them at a time (somtimes symbolized ⁿC_i.

It is also the ith element of the nth row (counting from 0) of Pascal's Triangle. , since

C (n, i) + C (n, i+1) = C (n+1, i+1)

---

The binomial theorem can be proven inductively when n is a for natural number.

Define F(p, q) = a^(q-p)b^p *q! / ((q-p)!p!)

Starting with some examples:

(a+b)⁰ = 1
       = 0!/(0!*0!)
       = sum(i=0..0, F(i, 0) )
(a+b)¹ = a + b
       = a¹b⁰*1!/(0!*1!) + a⁰b¹ *1!/(0!*1!)
       = sum(i=0..1, F(i, 1) )
(a+b)² = a² + 2ab + b²
       = a²b⁰*2!/(0!*2!) + 2!/(1!*1!)*a¹b¹ + 1!/(0!*1!)*a⁰b²
       = sum(i=0..2, F(i, 2) )
(a+b)³ = a³ + 2a²b + 2ab² + b³
       = a³b⁰*3!/(0!*3!) + a²b¹*3!/(2!*1!) + a¹b²*3!/(1!*2!) + a⁰b³*3!/(0!*3!)
       = sum(i=0..3, F(i, 3) )

Enough of that.   We now say for some m>=0 (such as the examples above),

(a + b)^m = sum (i=0..m, F(i, m))
         = sum (i=0..m, a^(m-i)bⁱ * m! / ((m-i)!i!)))

If we can show that

(a + b)^(m+1) = sum (i=0..m+1, a^((m+1)-i)bⁱ * (m+1)! / ((m+1)-i)!i! )
             = sum (i=0..m+1, F(i, m+1) )

we have proven our theorem.

To do this, we expand (a + b)^(m+1):

(a + b)^(m+1) = (a + b)(a + b)^m
            = (a + b) * sum (i=0..m, a^(m-i)bⁱ*m!/((m-i)!i!))
            = a * sum (i=0..m, a^(m-i)bⁱ*m!/((m-i)!i!))      + b * sum (i=0..m,   a^(m-i)bⁱ*m!  / ((m-i)!i!))
            = sum (i=0..m, a^(m-i+1)bⁱ*m!/((m-i)!i!))        +     sum (i=0..m,   a^(m-i)bⁱ⁺¹*m! / ((m-i)!i!))
            = a^{(m+1) +} sum (i=1..m, a^(m-i+1)bⁱ*m!/((m-i)!i!)) +     sum (i=0..m-1, a^(m-i)bⁱ⁺¹*m! / ((m-i)!i!)) + b^(m+1)

Now let's let j=i+1 (thus i = j-1) in all the terms of the second summation.

= a^{(m+1) +} sum (i=1..m, a^(m-i+1)bⁱ*m!/((m-i)!i!)) + sum (j=1..m, a^(m-j+1)b^j*m!/((m-j+1)!(j-1)!)) + b^(m+1)

The next step may look like we're trying to "pull a fast one", but it's perfectly valid!
We have labeled the variable in the second summation "j",  but its scope is only within that summation, and
we might as well relabel it "i".

= a^{(m+1) +} sum (i=1..m, a^(m-i+1)bⁱ*m!/((m-i)!i!)) + sum (i=1..m, a^(m-i+1)bⁱ*m!/((m-i+1)!(i-1)!)) + b^(m+1)

It wasn't absolutely necessary to do that, but it makes the next step a little clearer.
We pair off the term for each value of "i" in the first summation with the term for the corresponding value of "i" in the second summation.

(a + b)^(m+1)  = a^{(m+1) +} sum (i=1..m, a^(m-i+1)bⁱ * m! / ((m-i)!i!) + a^(m-i+1)bⁱ * m! / ((m-i+1)!(i-1)!) ) + b^(m+1)

(a + b)^(m+1)  = a^{(m+1) +} sum (i=1..m, a^(m-i+1)bⁱ * (m! / ((m-i+1)!(i-1)!) + m! / ((m-i)!i!)) ) + b^(m+1)

We have to spend some effort reducing the formula for our coefficients:

m!/((m-i+1)!(i-1)!)+m!/((m-i)!i!) = m!/((m-i+1)(m-i)!(i-1)!)+m!/((m-i)!i(i-1)!)

                                  = m! / ((m-i)!*(i-1)!) * (1/(m-i+1) + 1/i)

                                  = m! / ((m-i)!*(i-1)!) * (m-i+1+i) / (i*(m-i+1))

                                  = m! / ((m-i)!*(i-1)!) * (m+1) / (i*(m-i+1))

                                  = m!*(m+1) / ((m-i)!*(m-i+1)*i*(i-1)!)

                                  = (m+1)! / ((m-i+1)!*i!)

                                  = (m+1)! / ((m+1-i)!*i!)
 

So,

(a + b)^(m+1) = a^{(m+1) +} sum (i=1..m, a^(m+1-i)bⁱ * (m+1)! / (m+1-i)!i! ) + b^(m+1)
            = a^{(m+1) +} sum (i=1..m, F(i, m+1) ) + b^(m+1)

Finally, since

a^(m+1)= a^(m+1-0)b⁰*(m+1)!/((m+1-0)!0!) = F(0, m+1)

and

b^(m+1)= b^(m+1-0)a⁰*(m+1)!/(m+1-0)!0! = F(m+1, m+1)

we can collapse the beginning and ending terms into our formula:

(a + b)^(m+1) = sum (i=0..m+1, F(i, m+1) )

Which was to be proven.

---

To derive the binomial formula for rational n, remember the well-known result

(1-x^p) = (1-x)*sum(i=0..p, xⁱ)

which we can reasily convert to

(1-x^p)/(1-x) = sum(i=0..p, xⁱ)

Restructing ourselves to -1 < x < 1, we can take the limit of both sides as p-> infinity

1/(1-x) = sum(i=0..infinity, xⁱ) = 1 + x + x² + x³ + ...

We have a slightly different way of expressing the binomial theorem in combinatorics. Let n be a positive integer. Then for all x and y,

(x + y)^n = sigma (n) x^k y^n-k,
                               (k)

where the sum is taken from k=0 to k=n, and (n) is is a binomial coefficient.
                                                                                 (k)

--back to combinatorics--

Okay and for fractional powers there is another version of the binomial theorem. The first thing to notice is that the r^th binomial coefficient can be written as
(n(n-1)(n-2)(n-3)...(n-r+1))/r!
So if instead of ⁿC_k you use the above formula for the binomial coefficients you will end up with an infinite binomial series for any power.

Here's an example. Consider (1-x)^-1. Its easy to show using the above expression for the binomial coefficients(with n = -1) that the series expansion here is
1+x+x²+x³ + .....

Of course this form of the theorem cannot be proved by induction. The Taylor's Theorem could be used though.