What is the coefficient of \(x^7\) in the expansion of \((x + 2)^{10}\)? Computing it directly (multiplying ten factors and tracking every term) takes dozens of operations. The binomial theorem reduces this to one line, and the coefficients that show up are exactly the \(\binom{n}{r}\) of Pascal’s triangle that we saw in the previous article.
The expansion of \((a+b)^n\) for integer \(n\) is not Newton’s: it was known centuries before him, with the same coefficients as the triangle. Isaac Newton’s contribution, between 1664 and 1665, was to extend the formula to any real exponent, including fractional and negative ones. In that case the sum does not end: \((1+x)^{1/2} = 1 + \frac{1}{2}x - \frac{1}{8}x^2 + \frac{1}{16}x^3 - \cdots\) is an infinite sum, the binomial series, valid for \(|x| < 1\). This article deals with the integer-exponent case, which is the one combinatorics uses.
Why the binomial theorem? #
The binomial theorem shows up in many places in computing and mathematics:
- Probability: the binomial distribution (a model of \(n\) independent experiments with success probability \(p\)) writes \((p + q)^n\) as a sum of terms \(\binom{n}{k} p^k q^{n-k}\), where each term is the probability of exactly \(k\) successes.
- Numerical approximations: for \(|x| \ll 1\), the expansion \((1+x)^n \approx 1 + nx + \binom{n}{2}x^2 + \cdots\) underlies numerical methods and Taylor series in calculus.
- Computer algebra: SymPy implements
expand((a+b)**n)with multinomial coefficients, the generalization of the binomial theorem, andexpandhas already appeared on the site in the section on creating polynomials with SymPy. Knowing the formula lets you predict and debug symbolic results. - Combinatorial identities: substituting specific values for \(a\) and \(b\) yields identities about binomial coefficients, including the Row Theorem (\(\sum \binom{n}{k} = 2^n\)), presented in the previous article, whose most direct proof comes from here.
- Polynomial kernels in machine learning: the number of terms in \((x_1 + x_2 + \cdots + x_d)^n\) is directly tied to combinations with repetition, and the binomial is the case \(d = 2\).
The Map of the Theorem #
The diagram below shows how the concepts in this article connect: the binomial theorem generates the general term, which lets us extract specific coefficients, and special cases produce identities about rows of Pascal’s triangle.
flowchart TD
TH["Binomial theorem
(a+b)ⁿ = Σ C(n,r) aⁿ⁻ʳ bʳ"] --> TG["General term
T_{r+1} = C(n,r) aⁿ⁻ʳ bʳ"]
TH --> SUB["Special cases
by substitution"]
TG --> COEF["Extract the coefficient
of xᵏ: solve n−r=k"]
SUB --> I1["a=b=1
∑ C(n,k) = 2ⁿ"]
SUB --> I2["a=1, b=−1
∑ (−1)ʳ C(n,r) = 0"]
I1 --> PAL["Recovers the Row
Theorem (previous article)"]
The Binomial Theorem #
Before stating the theorem, look at the expansions for small \(n\): the coefficients in each row are exactly the values of the corresponding row of Pascal’s triangle.
| \(n\) | Expansion |
|---|---|
| 0 | \(1\) |
| 1 | \(a + b\) |
| 2 | \(a^2 + 2ab + b^2\) |
| 3 | \(a^3 + 3a^2b + 3ab^2 + b^3\) |
| 4 | \(a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4\) |
The figure below makes the correspondence for \(n = 4\): each number in the row drops onto the term it is the coefficient of, and below each term appears the corresponding binomial coefficient.
For all \(a, b \in \mathbb{R}\) and every integer \(n \geq 0\):
$$(a + b)^n = \sum_{r=0}^{n} \binom{n}{r} a^{n-r} b^r$$Proof by Mathematical Induction #
Mathematical induction (a proof technique that treats the base case and the inductive step separately) is the natural tool here, since the binomial theorem claims something for every integer \(n \geq 0\). Since the base is \(n = 0\), we use the generalized version of the principle, with \(n_0 = 0\) (in the convention of this collection of series, \(0 \notin \mathbb{N}\)).
Base case (\(n=0\)): \((a+b)^0 = 1 = \binom{0}{0} a^0 b^0\). ✓
Inductive hypothesis (IH): suppose that, for some integer \(k \geq 0\), \((a+b)^k = \sum_{r=0}^{k}\binom{k}{r}a^{k-r}b^r\) holds.
Inductive step (\(n = k+1\)): multiplying both sides of the IH by \((a+b)\):
$$ (a+b)^{k+1} = (a+b)\sum_{r=0}^{k}\binom{k}{r}a^{k-r}b^r = \sum_{r=0}^{k}\binom{k}{r}a^{k+1-r}b^r + \sum_{r=0}^{k}\binom{k}{r}a^{k-r}b^{r+1} $$Reindexing the second sum with \(r \to r-1\):
$$= \sum_{r=0}^{k}\binom{k}{r}a^{k+1-r}b^r + \sum_{r=1}^{k+1}\binom{k}{r-1}a^{k+1-r}b^r$$The extreme terms (\(r=0\) and \(r=k+1\)) contribute \(a^{k+1}\) and \(b^{k+1}\); for the intermediate ones, Pascal’s rule gives \(\binom{k}{r-1} + \binom{k}{r} = \binom{k+1}{r}\):
$$= \sum_{r=0}^{k+1}\binom{k+1}{r}a^{k+1-r}b^r$$Therefore, \((a+b)^n = \sum_{r=0}^{n} \binom{n}{r} a^{n-r} b^r\) for every integer \(n \geq 0\), which is what we wanted to prove. \(\blacksquare\)
General Term #
The expansion of \((a+b)^n\) has \(n+1\) terms. To identify a specific term without expanding everything, we use the general term formula:
The \((r+1)\)-th term of the expansion of \((a+b)^n\) is:
$$T_{r+1} = \binom{n}{r} a^{n-r} b^r, \qquad r = 0, 1, \ldots, n$$Identities from Special Cases #
Substituting specific values for \(a\) and \(b\) in the binomial theorem gives identities about binomial coefficients.
This result coincides with the Row Theorem from the previous article: the binomial theorem gives its most direct proof.
For \(n \geq 1\) (with \(n = 0\), the sum has a single term and equals 1):
$$\sum_{r=0}^n (-1)^r\binom{n}{r} = 0$$Corollary: adding the even and odd indices separately and using Identity 1:
$$\binom{n}{0} + \binom{n}{2} + \cdots = \binom{n}{1} + \binom{n}{3} + \cdots = 2^{n-1}$$Worked Examples #
The diagram below summarizes the procedure for applying the general term: it branches depending on whether the goal is to fully expand the binomial or to isolate the coefficient of a specific term.
flowchart TD
A["Write (a+b)ⁿ:
identify a, b and n"] --> B["General term:
T_{r+1} = C(n,r) aⁿ⁻ʳ bʳ"]
B --> C{"What is the goal?"}
C -->|"Full expansion"| D["Compute r = 0, 1, …, n
and add the n+1 terms"]
C -->|"Coefficient of aᵏbʲ"| E["Solve n − r = k
(or r = j)"]
E --> F{"r ∈ {0, …, n}?"}
F -->|"Yes"| G["Compute T_{r+1} = C(n,r) aⁿ⁻ʳ bʳ"]
F -->|"No"| H["Coefficient = 0
(the term does not exist)"]
Full expansion of \((x+3)^4\) #
Problem: Expand \((x+3)^4\) using the binomial theorem.
Solution: The general term is \(T_{r+1} = \binom{4}{r} x^{4-r} 3^r\). Computing each term:
| \(r\) | \(\binom{4}{r}\) | \(x^{4-r}\) | \(3^r\) | Term |
|---|---|---|---|---|
| 0 | 1 | \(x^4\) | 1 | \(x^4\) |
| 1 | 4 | \(x^3\) | 3 | \(12x^3\) |
| 2 | 6 | \(x^2\) | 9 | \(54x^2\) |
| 3 | 4 | \(x\) | 27 | \(108x\) |
| 4 | 1 | 1 | 81 | \(81\) |
Coefficient of \(x^2\) in \(\left(x^3 - \dfrac{1}{x^2}\right)^9\) #
Problem: Find the coefficient of \(x^2\) in the expansion of \(\left(x^3 - \dfrac{1}{x^2}\right)^9\).
Solution: The general term is:
$$T_{r+1} = \binom{9}{r}(x^3)^{9-r}\left(-\frac{1}{x^2}\right)^r = \binom{9}{r}(-1)^r x^{27-3r-2r} = \binom{9}{r}(-1)^r x^{27-5r}$$For the term to contain \(x^2\), we need \(27 - 5r = 2\), that is, \(r = 5\):
$$T_6 = \binom{9}{5}(-1)^5 x^2 = 126 \cdot (-1) \cdot x^2 = -126x^2$$The coefficient of \(x^2\) is \(\mathbf{-126}\).
Python: extracting coefficients with math.comb
math.comb
The general term formula translates directly into code. To recover the coefficient of \(x^7\) in \((x + 2)^{10}\) (the opening question) we just solve \(10 - r = 7 \Rightarrow r = 3\) and compute:
from math import comb
def binomial_coef(b, n, exp_a):
"""Coefficient of a^exp_a in the expansion of (a + b)^n."""
r = n - exp_a # exponent of b in the term
return comb(n, r) * (b ** r)
# Coefficient of x^7 in (x + 2)^10
print(binomial_coef(b=2, n=10, exp_a=7)) # 960
# Check: the sum of row 10 must be 2^10 = 1024
print(sum(binomial_coef(1, 10, k) for k in range(11))) # 1024The second block checks Identity 1: substituting \(a = b = 1\), the sum of all the coefficients of \((1+1)^{10}\) must give \(2^{10} = 1{,}024\).
Summary Table #
The table below gathers all the results proved in this article for quick reference.
| Result | Formula |
|---|---|
| Binomial theorem | \(\displaystyle(a+b)^n = \sum_{r=0}^{n} \binom{n}{r} a^{n-r} b^r\) |
| General term | \(T_{r+1} = \binom{n}{r} a^{n-r} b^r\) |
| Identity 1 (\(a=b=1\)) | \(\displaystyle\sum_{r=0}^n \binom{n}{r} = 2^n\) |
| Identity 2 (\(a=1, b=-1\), \(n \geq 1\)) | \(\displaystyle\sum_{r=0}^n (-1)^r\binom{n}{r} = 0\) |
| Corollary (parities, \(n \geq 1\)) | \(\displaystyle\sum_{r \text{ even}} \binom{n}{r} = \sum_{r \text{ odd}} \binom{n}{r} = 2^{n-1}\) |
Exercises #
The following exercises apply the binomial theorem to expansions, extraction of specific terms, and proofs of identities. They are ordered from simplest to most complex.
Exercise 1: Expansions
Expand: (a) \((2a - 3b)^3\) (b) \((2y + 3x)^4\) (c) \(\left(\dfrac{1}{y} - y\right)^6\)
Solution
(a) \(T_{r+1} = \binom{3}{r}(2a)^{3-r}(-3b)^r\):
$$8a^3 - 36a^2b + 54ab^2 - 27b^3$$(b) \(T_{r+1} = \binom{4}{r}(2y)^{4-r}(3x)^r\):
$$16y^4 + 96y^3x + 216y^2x^2 + 216yx^3 + 81x^4$$(c) \(T_{r+1} = \binom{6}{r}(y^{-1})^{6-r}(-y)^r = \binom{6}{r}(-1)^r y^{2r-6}\):
$$y^{-6} - 6y^{-4} + 15y^{-2} - 20 + 15y^2 - 6y^4 + y^6$$
Exercise 2: Sixth term
Compute the 6th term of: (a) \(\left(1 - \dfrac{1}{b}\right)^7\) (b) \(\left(3x^2y - \dfrac{1}{3}\right)^9\)
Solution
The 6th term uses \(r = 5\):
(a) \(T_6 = \binom{7}{5}(1)^2\left(-\dfrac{1}{b}\right)^5 = -\dfrac{21}{b^5}\)
(b) \(T_6 = \binom{9}{5}(3x^2y)^4\left(-\dfrac{1}{3}\right)^5 = 126 \cdot 81x^8y^4 \cdot \left(-\dfrac{1}{243}\right) = \mathbf{-42x^8y^4}\)
Exercise 3: Sum of the coefficients
Compute the sum of the coefficients of all the terms of \(\left(x^3 - \dfrac{1}{2x}\right)^{12}\).
Solution
The sum of the coefficients is the value of the expression at \(x = 1\):
$$\left(1 - \frac{1}{2}\right)^{12} = \left(\frac{1}{2}\right)^{12} = \mathbf{\frac{1}{4{,}096}}$$
Exercise 4: Terms independent of \(x\)
Find the term independent of \(x\) in: (a) \(\left(x^2 + \dfrac{1}{x^2}\right)^6\) (b) \(\left(x^2 + \dfrac{1}{x}\right)^9\)
Solution
(a) \(T_{r+1} = \binom{6}{r}x^{12-4r}\). Independent: \(12 - 4r = 0 \Rightarrow r = 3\). Term: \(\binom{6}{3} = \mathbf{20}\)
(b) \(T_{r+1} = \binom{9}{r}x^{18-3r}\). Independent: \(18 - 3r = 0 \Rightarrow r = 6\). Term: \(\binom{9}{6} = \mathbf{84}\)
Exercise 5: Why does \((x + x^{-1})^{2n+1}\) have no independent term?
Proof
\(T_{r+1} = \binom{2n+1}{r} x^{2n+1-2r}\). To be independent of \(x\), we would need \(2n+1-2r = 0 \Rightarrow 2r = 2n+1\). This is impossible: the left side is even and the right side is odd. Therefore, \((x + x^{-1})^{2n+1}\) has no term independent of \(x\), which is what we wanted to prove. \(\blacksquare\)
Exercise 6: Proof: \(\left(1 + \dfrac{1}{n}\right)^n > 2\) for \(n \geq 2\)
Proof
By the binomial theorem with \(a = 1\) and \(b = \frac{1}{n}\):
$$\left(1 + \frac{1}{n}\right)^n = \sum_{k=0}^n \binom{n}{k}\frac{1}{n^k}$$The terms \(k=0\) and \(k=1\) already add up to \(1 + 1 = 2\). For \(n \geq 2\), there are additional strictly positive terms. Therefore, \(\left(1+\frac{1}{n}\right)^n > 2\) for \(n \geq 2\), which is what we wanted to prove. \(\blacksquare\)
The same expansion is one of the classic routes to the number \(e\): as \(n\) grows, \(\left(1+\frac{1}{n}\right)^n\) increases without ever exceeding 3 and converges to \(e = 2.71828\ldots\) (for \(n = 1000\), it is already 2.7169…).
Next Steps #
With the binomial theorem we close the series “The Art of Counting”. We started from the sum and product rules, built permutations, arrangements and combinations (with and without repetition), studied the binomial coefficients and Pascal’s triangle, and arrived at the theorem that unites algebra and combinatorics. The map of all the Discrete Mathematics content on the site is in “Discrete Mathematics: Introduction and Roadmap”.
Combinatorics answers questions of the type “how many?”, but many problems in computing also ask “how are they connected?”. To answer that, graph theory comes in, the mathematics of networks, paths and connections. The next article, The Mathematics of Connections: Graph Theory from Scratch, introduces graphs from scratch: from the Bridges of Königsberg to modern search algorithms.
Series Summary #
The table below gathers all the counting techniques in the series, with the formula and the situation in which to use each one.
| Technique | Formula | When to use |
|---|---|---|
| Sum rule | \(|A| + |B|\) | Exclusive choices (“or”) |
| Product rule | \(|A| \cdot |B|\) | Independent stages (“and”) |
| Permutation | \(n!\) | Order everything |
| Circular permutation | \((n-1)!\) | Order around a circle |
| Permutation with repetition | \(\dfrac{n!}{n_1!\cdots n_k!}\) | Order with identical items |
| Arrangement | \(\dfrac{n!}{(n-r)!}\) | Order \(r\) out of \(n\) |
| Arrangement with repetition | \(n^r\) | Sequence with repetition |
| Combination | \(\dbinom{n}{r}\) | Select \(r\) out of \(n\) |
| Combination with repetition | \(\dbinom{n+r-1}{r}\) | Select with repetition |
| Binomial theorem | \(\displaystyle\sum_{r=0}^n\binom{n}{r}a^{n-r}b^r\) | Expand \((a+b)^n\) |
