A law of
algebra, showing how to expand the term
(a + b)n
That is,
(a + b)n = sum (i=0..n, a(n-i)bi *
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)n = 1 + sum [i=1..infinity, xi*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)n = sum (i = 0..infinity, C(n, i) aibn-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 nCi.
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)bp
*q! / ((q-p)!p!)
Starting with some examples:
(a+b)0 = 1
= 0!/(0!*0!)
= sum(i=0..0, F(i,
0) )
(a+b)1 = a + b
= a1b0*1!/(0!*1!)
+ a0b1 *1!/(0!*1!)
= sum(i=0..1, F(i,
1) )
(a+b)2 = a2 + 2ab + b2
= a2b0*2!/(0!*2!)
+ 2!/(1!*1!)*a1b1 + 1!/(0!*1!)*a0b2
= sum(i=0..2, F(i,
2) )
(a+b)3 = a3 + 2a2b + 2ab2
+ b3
= a3b0*3!/(0!*3!)
+ a2b1*3!/(2!*1!) + a1b2*3!/(1!*2!)
+ a0b3*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)bi * m! / ((m-i)!i!)))
If we can show that
(a + b)(m+1) = sum (i=0..m+1, a((m+1)-i)bi
* (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)bi*m!/((m-i)!i!))
= a * sum (i=0..m, a(m-i)bi*m!/((m-i)!i!))
+ b * sum (i=0..m, a(m-i)bi*m!
/ ((m-i)!i!))
= sum (i=0..m, a(m-i+1)bi*m!/((m-i)!i!))
+ sum (i=0..m, a(m-i)bi+1*m!
/ ((m-i)!i!))
= a(m+1) + sum (i=1..m, a(m-i+1)bi*m!/((m-i)!i!))
+ sum (i=0..m-1, a(m-i)bi+1*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)bi*m!/((m-i)!i!))
+ sum (j=1..m, a(m-j+1)bj*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)bi*m!/((m-i)!i!))
+ sum (i=1..m, a(m-i+1)bi*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)bi * m! / ((m-i)!i!) + a(m-i+1)bi
*
m! / ((m-i+1)!(i-1)!) ) + b(m+1)
(a + b)(m+1) = a(m+1) + sum (i=1..m,
a(m-i+1)bi * (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)bi
* (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)b0*(m+1)!/((m+1-0)!0!)
= F(0, m+1)
and
b(m+1)= b(m+1-0)a0*(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-xp) = (1-x)*sum(i=0..p, xi)
which we can reasily convert to
(1-xp)/(1-x) = sum(i=0..p, xi)
Restructing ourselves to -1 < x < 1, we can take the limit of both sides as p-> infinity
1/(1-x) = sum(i=0..infinity, xi) = 1 + x + x2 + x3 + ...