The Binomial Theorem

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 proved by induction — Pascal's identity (nk)+(nk−1)=(n+1k)\binom{n}{k}+\binom{n}{k-1}=\binom{n+1}{k} is the inductive step, and row nn of Pascal's triangle is drawn live.

(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: 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.

1. Number Systems