Polynomials and Factoring expanded (a + b)² and (a + b)³ by hand. (a + b)⁵ is possible with patience, and (a + b)¹² is not: multiplying out twelve brackets means 2¹² = 4096 products before any collecting starts. The theorem below skips all of it.
(a + b)⁰ = 1
(a + b)¹ = a + b
(a + b)² = a² + 2ab + b²
(a + b)³ = a³ + 3a²b + 3ab² + b³
(a + b)⁴ = a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴
in every line the power of a falls and the power of b rises,
and the two always total the exponent on the left
Stripping out the coefficients leaves a triangle in which every entry is the sum of the two directly above it, with 1s down both edges. It is called Pascal's triangle, and row n holds the coefficients of (a + b)ⁿ.
n = 0 1
n = 1 1 1
n = 2 1 2 1
n = 3 1 3 3 1
n = 4 1 4 6 4 1
n = 5 1 5 10 10 5 1
n = 6 1 6 15 20 15 6 1
15 = 5 + 10: each entry is the sum of the two above it
Definition · Binomial coefficientFor integers 0 ≤ k ≤ n, C(n, k) = n!/(k!(n - k)!), read "n choose k". It is also written with n above k in a single pair of brackets. The factorials are the ones from “Sequences and Recursion”, with 0! = 1.
Example · Computing C(9, 4) without computing 9!C(9,4) = 9!/(4!5!). The 5! cancels most of the 9!, leaving (9·8·7·6)/(4·3·2·1) = 3024/24 = 126. Four factors on top because k = 4, and four below. The cancelling is not a shortcut for the lazy: 9! is 362880, and there is no reason to write it down.
Theorem · The binomial theoremFor any numbers a, b and any nonnegative integer n, (a + b)ⁿ = Σ C(n,k) aⁿ⁻ᵏ bᵏ, the sum running over k from 0 to n. Written out, that is aⁿ + C(n,1)aⁿ⁻¹b + C(n,2)aⁿ⁻²b² + … + C(n,n-1)abⁿ⁻¹ + bⁿ.
Why the coefficient of aⁿ⁻ᵏbᵏ is C(n,k): expanding n brackets means taking one letter from each and multiplying, then adding every such product. A product ends up as aⁿ⁻ᵏbᵏ exactly when the b was taken from k of the brackets, and the number of ways to choose which k is C(n,k). Every one of those choices contributes 1, so they add to C(n,k).
That is also why the triangle's rule works: a choice of k brackets out of n either uses the last bracket, leaving k - 1 to choose from the first n - 1, or does not, leaving k to choose from n - 1. So C(n,k) = C(n-1,k-1) + C(n-1,k), which is the sum-of-the-two-above rule stated in symbols. The triangle is also symmetric, because C(n,k) = C(n,n-k): choosing k brackets to give b is the same act as choosing the other n - k to give a.
Example · The signs of (a - b)⁴(a - b)⁴ = a⁴ - 4a³b + 6a²b² - 4ab³ + b⁴. The coefficients are row 4 unchanged; the signs come from (-b)ᵏ, so terms with odd k are negative. The last term is (-b)⁴ = +b⁴, which is the one people expect to be negative.
Setting a = b = 1 turns the theorem into 2ⁿ = C(n,0) + C(n,1) + … + C(n,n): each row of Pascal's triangle adds up to a power of two. Row 5 is 1, 5, 10, 10, 5, 1, totalling 32. It is a check on a row you have just written, and it is also the statement that a set of n things has 2ⁿ subsets.