The Binomial Theorem

See the triangle made by the coefficients of expanded powers. Follow one whole row being computed.

A binomial coefficient counts ways to choose. Each entry in the triangle is the sum of the two above it. That addition rule is the heart of the induction step. A whole row adds up to a power of two.

For example, toss two coins and count the heads: zero, one, or two. The counts go one way, two ways, one way. That is the triangle's second row, exactly.

(x+y)n=∑k=0n(nk)xn−kyk(x+y)^n = \sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^k
(nk)+(nk−1)=(n+1k)\binom{n}{k}+\binom{n}{k-1}=\binom{n+1}{k}
∑k=0n(nk)=2n\sum_{k=0}^{n}\binom{n}{k} = 2^n

Part of these learning paths

Examples & Exercises

Let x,yx, y be numbers (real or complex) and n≥0n \geq 0 an integer.

Prove the binomial theorem (x+y)n=∑k=0n(nk)xn−kyk(x+y)^n = \sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^k by induction on nn.

(x+y)n=∑k=0n(nk)xn−kyk(x+y)^n = \sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^k
Row n=4n = 4: 1, 4, 6, 4, 11,\ 4,\ 6,\ 4,\ 1 — the coefficients in the expansion of (x+y)4(x+y)^4.
Show proof

  1. First verify Pascal's identity (nk)+(nk−1)=(n+1k)\binom{n}{k}+\binom{n}{k-1}=\binom{n+1}{k} (1≤k≤n1 \leq k \leq n), which the induction step will use. Substituting (nk)=n!k!(n−k)!\binom{n}{k}=\frac{n!}{k!(n-k)!} gives n!k!(n−k)!+n!(k−1)!(n−k+1)!\frac{n!}{k!(n-k)!}+\frac{n!}{(k-1)!(n-k+1)!}; factoring out n!(k−1)!(n−k)!\frac{n!}{(k-1)!(n-k)!} yields n!(k−1)!(n−k)!(1k+1n−k+1)=n!(k−1)!(n−k)!⋅n+1k(n−k+1)=(n+1)!k!(n+1−k)!=(n+1k)\frac{n!}{(k-1)!(n-k)!}\left(\frac1k+\frac1{n-k+1}\right) = \frac{n!}{(k-1)!(n-k)!}\cdot\frac{n+1}{k(n-k+1)} = \frac{(n+1)!}{k!(n+1-k)!} = \binom{n+1}{k}.

  2. Base case n=0n = 0: use the convention 00=10^0 = 1 here (the empty product) — (x+y)0=1(x+y)^0 = 1 even when x+y=0x + y = 0, and the factors x0,y0x^0, y^0 are 11 even when x=0x = 0 or y=0y = 0. The left side is (x+y)0=1(x+y)^0 = 1, and the right side has only the term k=0k = 0, giving (00)x0y0=1⋅1⋅1=1\binom{0}{0}x^0y^0 = 1\cdot 1\cdot 1 = 1 — it holds.

  3. Assume the formula holds for nn. Then (x+y)n+1=(x+y)(x+y)n(x+y)^{n+1} = (x+y)(x+y)^n, and substituting the induction hypothesis gives ∑k=0n(nk)xn+1−kyk+∑k=0n(nk)xn−kyk+1\sum_{k=0}^{n}\binom{n}{k}x^{n+1-k}y^k + \sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^{k+1}.

  4. Reindexing the second sum with j=k+1j = k+1 gives ∑j=1n+1(nj−1)xn+1−jyj\sum_{j=1}^{n+1}\binom{n}{j-1}x^{n+1-j}y^j (renaming kk to jj in the first sum as well).

    For 1≤j≤n1 \leq j \leq n the coefficient of xn+1−jyjx^{n+1-j}y^j is (nj)+(nj−1)\binom{n}{j}+\binom{n}{j-1}, which equals (n+1j)\binom{n+1}{j} by Pascal's identity.

    The boundary terms are (n0)=1=(n+10)\binom{n}{0} = 1 = \binom{n+1}{0} at j=0j = 0 and (nn)=1=(n+1n+1)\binom{n}{n} = 1 = \binom{n+1}{n+1} at j=n+1j = n+1, so the whole sum is ∑j=0n+1(n+1j)xn+1−jyj\sum_{j=0}^{n+1}\binom{n+1}{j}x^{n+1-j}y^j — exactly the formula for n+1n+1.

  5. The base case and the inductive step give the binomial theorem for every n≥0n \geq 0. The crux is Pascal's identity — the recurrence of the binomial coefficients meshes exactly with the inductive step of multiplying by one more (x+y)(x+y).

Prove that ∑k=0n(nk)=2n\sum_{k=0}^{n}\binom{n}{k} = 2^n for every integer n≥0n \geq 0.

∑k=0n(nk)=2n\sum_{k=0}^{n}\binom{n}{k} = 2^n
The sum of row n=4n = 4: 1+4+6+4+1=16=241+4+6+4+1 = 16 = 2^4.
Show proof

  1. Substitute x=1x = 1, y=1y = 1 into the binomial theorem. The left side becomes (1+1)n=2n(1+1)^n = 2^n.

  2. The right side is ∑k=0n(nk)1n−k1k=∑k=0n(nk)\sum_{k=0}^{n}\binom{n}{k}1^{n-k}1^k = \sum_{k=0}^{n}\binom{n}{k} (powers of 11 are 11). Hence ∑k=0n(nk)=2n\sum_{k=0}^{n}\binom{n}{k} = 2^n — this is why each row of Pascal's triangle sums to a power of 22.

Prove that ∑k=0n(−1)k(nk)=0\sum_{k=0}^{n}(-1)^k\binom{n}{k} = 0 for every integer n≥1n \geq 1.

∑k=0n(−1)k(nk)=0(n≥1)\sum_{k=0}^{n}(-1)^k\binom{n}{k} = 0 \quad (n \geq 1)
Row n=4n = 4: 1−4+6−4+1=01-4+6-4+1 = 0 — alternating signs cancel the sum.
Show proof

  1. Substitute x=1x = 1, y=−1y = -1 into the binomial theorem. The left side is (1+(−1))n=0n(1+(-1))^n = 0^n, and 0n=00^n = 0 since n≥1n \geq 1 (n=0n = 0 is excluded because 000^0 is conventionally 11).

  2. The right side is ∑k=0n(nk)1n−k(−1)k=∑k=0n(−1)k(nk)\sum_{k=0}^{n}\binom{n}{k}1^{n-k}(-1)^k = \sum_{k=0}^{n}(-1)^k\binom{n}{k}. Hence ∑k=0n(−1)k(nk)=0\sum_{k=0}^{n}(-1)^k\binom{n}{k} = 0 — alternating signs cancel every row of Pascal's triangle to 00.

2. Number Systems