00.12.02 · precalc / induction-combinatorics

Binomial theorem and Pascal's triangle

shipped3 tiersLean: none

Anchor (Master): Pascal 1654 Traite du triangle arithmetique; Newton 1665 De analysi; Stanley Enumerative Combinatorics Vol. 1

Intuition [Beginner]

When you multiply $(a + b)$ by itself, the result has a predictable set of coefficients. The binomial theorem exists because multiplying out $(a + b)^{n}$ one factor at a time is slow and error-prone — the theorem gives you every coefficient at once. Multiply $(a + b)$ by itself to get $a^{2} + 2 ab + b^{2}$ with coefficients $1, 2, 1$ . One more multiplication gives $(a + b)^{3} = a^{3} + 3 a^{2} b + 3 a b^{2} + b^{3}$ with coefficients $1, 3, 3, 1$ .

Arrange the coefficients in a triangle. Row 0 is just $1$ . Row 1 is $1, 1$ . Row 2 is $1, 2, 1$ . Each number is the sum of the two numbers directly above it.

$$\begin{array}{c} 1 \ 1 \quad 1 \ 1 \quad 2 \quad 1 \ 1 \quad 3 \quad 3 \quad 1 \ 1 \quad 4 \quad 6 \quad 4 \quad 1 \end{array}$$

This is Pascal's triangle. Row $n$ (starting from 0) gives every coefficient in the expansion of $(a + b)^{n}$ , letting you read off the answer without multiplying.

Visual [Beginner]

Pascal's triangle drawn as a pyramid of numbers, with each entry connected by lines to the two entries directly above it. Row 4 is highlighted to show its connection to the expansion of $(a + b)^{4}$ .

The picture encodes the addition rule: each number in the triangle is the sum of the two numbers above it, and each row gives the full set of coefficients for the corresponding power of $(a + b)$ .

Worked example [Beginner]

Expand $(x + 1)^{4}$ using Pascal's triangle.

Step 1. Identify row 4. Starting from row 0 and counting down: row 0 is $1$ , row 1 is $1, 1$ , row 2 is $1, 2, 1$ , row 3 is $1, 3, 3, 1$ , and row 4 is $1, 4, 6, 4, 1$ .

Step 2. Write the expansion using these five coefficients, with powers of $x$ decreasing and powers of $1$ increasing:

$(x + 1)^{4} = 1 \cdot x^{4} + 4 \cdot x^{3} \cdot 1 + 6 \cdot x^{2} \cdot 1^{2} + 4 \cdot x \cdot 1^{3} + 1 \cdot 1^{4} .$

Step 3. Simplify, since every power of $1$ is $1$ :

$x^{4} + 4 x^{3} + 6 x^{2} + 4 x + 1.$

What this tells us: the triangle gives every coefficient without having to multiply $(x + 1)$ by itself four times.

Check your understanding [Beginner]

Formal definition [Intermediate+]

Definition (binomial coefficient). For non-negative integers $n$ and $k$ with $0 \leq k \leq n$ , the binomial coefficient $(k n)$ (read " $n$ choose $k$ ") is defined by

$(k n) = \frac{n !}{k ! ( n - k )!},$

where $n! = n (n - 1) (n - 2) \dots 2 \cdot 1$ and $0! = 1$ .

The binomial coefficients count the number of ways to choose $k$ objects from a set of $n$ distinct objects, disregarding order. This counting interpretation gives $(k n)$ its combinatorial meaning and provides direct proofs of many identities without algebraic manipulation.

Pascal's recurrence. For $1 \leq k \leq n - 1$ :

$(k n) = (k - 1 n - 1) + (k n - 1) .$

This recurrence is the addition rule visible in the triangle: each entry equals the sum of the two entries above it. The proof by counting is direct — partition the $k$ -element subsets of ${1, 2, \dots, n}$ into those that contain element $n$ (there are $(k - 1 n - 1)$ ) and those that do not (there are $(k n - 1)$ ).

Counterexamples to common slips [Intermediate+]

Confusing $(k n)$ with $n^{k}$ . The binomial coefficient $(k n)$ counts subsets; $n^{k}$ counts sequences (with repetition and order). For $n = 3, k = 2$ : $(2 3) = 3$ but $3^{2} = 9$ .
Assuming $(a + b)^{n} = a^{n} + b^{n}$ . This holds only when $n = 1$ or when the ring has characteristic $n$ and every cross term vanishes. In $R [x, y]$ : $(a + b)^{2} = a^{2} + 2 ab + b^{2} \neq = a^{2} + b^{2}$ .
Off-by-one in row numbering. Row $n$ of Pascal's triangle corresponds to $(a + b)^{n}$ and has $n + 1$ entries. Row 0 is the single number 1, not the first row of $1, 1$ .

Key theorem with proof [Intermediate+]

Theorem (binomial theorem). For every positive integer $n$ and elements $a, b$ in a commutative ring:

$(a + b)^{n} = (0 n) a^{n} + (1 n) a^{n - 1} b + (2 n) a^{n - 2} b^{2} + \dots + (n n) b^{n} .$

In compact notation:

$(a + b)^{n} = k = 0 \sum n (k n) a^{n - k} b^{k} .$

Proof. By induction on $n$ , following the method established in 00.12.01.

Base case ( $n = 1$ ). $(a + b)^{1} = a + b = (0 1) a + (1 1) b$ . Both sides agree.

Inductive step. Assume the formula holds for $n = m$ :

$(a + b)^{m} = k = 0 \sum m (k m) a^{m - k} b^{k} .$

Multiply both sides by $(a + b)$ :

$(a + b)^{m + 1} = (a + b) k = 0 \sum m (k m) a^{m - k} b^{k} = k = 0 \sum m (k m) a^{m + 1 - k} b^{k} + k = 0 \sum m (k m) a^{m - k} b^{k + 1} .$

In the second sum, substitute $j = k + 1$ so that $k = j - 1$ and the index runs from $j = 1$ to $j = m + 1$ :

$= k = 0 \sum m (k m) a^{m + 1 - k} b^{k} + j = 1 \sum m + 1 (j - 1 m) a^{m + 1 - j} b^{j} .$

Separate the $k = 0$ term from the first sum and the $j = m + 1$ term from the second:

$= a^{m + 1} + k = 1 \sum m [(k m) + (k - 1 m)] a^{m + 1 - k} b^{k} + b^{m + 1} .$

By Pascal's recurrence, $(k m) + (k - 1 m) = (k m + 1)$ . The boundary terms satisfy $(0 m) = (0 m + 1) = 1$ and $(m m) = (m + 1 m + 1) = 1$ . Therefore:

$(a + b)^{m + 1} = k = 0 \sum m + 1 (k m + 1) a^{m + 1 - k} b^{k},$

which is the formula with $m + 1$ in place of $m$ . $□$

Bridge. The inductive proof of the binomial theorem builds toward the generating-function techniques of enumerative combinatorics, where $(1 + x)^{n}$ serves as the generating function for the sequence $(0 n), (1 n), \dots, (n n)$ . The foundational reason the proof works is that Pascal's recurrence is exactly the combinatorial identity that makes the induction close, and this is exactly the structure that appears again in 00.12.01 as the inductive proof method. Putting these together, the central insight is that the binomial theorem is simultaneously an algebraic identity in every commutative ring and a combinatorial identity about counting subsets, and the bridge is the interplay between these two interpretations.

Exercises [Intermediate+]

Exercise 5 (medium, symbolic).

Using the binomial theorem with $a = 1$ and $b = 1$ , show that the entries in row $n$ of Pascal's triangle sum to $2^{n}$ . Then prove the same identity directly by induction using Pascal's recurrence.

Hint

For the induction, assume $(0 m) + (1 m) + \dots + (m m) = 2^{m}$ and apply Pascal's recurrence to each interior term of row $m + 1$ .

Answer

Via the binomial theorem. Set $a = 1, b = 1$ in $(a + b)^{n} = \sum_{k = 0}^{n} (k n) a^{n - k} b^{k}$ . The left side is $(1 + 1)^{n} = 2^{n}$ , and the right side is $\sum_{k = 0}^{n} (k n)$ .

Direct induction. Base case $n = 0$ : $(0 0) = 1 = 2^{0}$ . Inductive step: assume $\sum_{k = 0}^{m} (k m) = 2^{m}$ . Then

$k = 0 \sum m + 1 (k m + 1) = 1 + k = 1 \sum m [(k - 1 m) + (k m)] + 1.$

By Pascal's recurrence the interior sum equals $2 \sum_{k = 0}^{m} (k m) - (0 m) - (m m) = 2 \cdot 2^{m} - 2$ . Adding the boundary terms $1 + 1$ gives $2^{m + 1}$ .

Rubric: full credit for either approach; both for distinction.

Advanced results [Master]

Theorem 1 (generalized binomial theorem — Newton). For any real number $α$ and $∣ x ∣ < 1$ :

$(1 + x)^{α} = k = 0 \sum \infty (k α) x^{k},$

where the generalized binomial coefficient is $(k α) = α (α - 1) (α - 2) \dots (α - k + 1) / k!$ . When $α = n$ is a non-negative integer, the series terminates at $k = n$ and reduces to the ordinary binomial theorem. For negative and fractional $α$ , the series is infinite and converges absolutely for $∣ x ∣ < 1$ . Newton discovered this in 1665–1666 ^{[Newton 1665]}; the rigorous convergence proof is due to Abel 1826 ^{[Abel 1826]}.

Theorem 2 (generating function for binomial coefficients). For fixed $n$ , the polynomial $(1 + x)^{n}$ is the ordinary generating function for the sequence $(0 n), (1 n), \dots, (n n)$ : the coefficient of $x^{k}$ in $(1 + x)^{n}$ is $(k n)$ . This identification converts combinatorial identities about binomial coefficients into algebraic manipulations of polynomials. The Chu-Vandermonde identity (Exercise 7) is the prototypical example: it is the coefficient-of- $x^{r}$ reading of $(1 + x)^{m + n} = (1 + x)^{m} (1 + x)^{n}$ .

Theorem 3 (Catalan numbers and binomial coefficients). The Catalan numbers $C_{n} = \frac{1}{n + 1} (n 2 n)$ count well-formed parenthesizations of $n + 1$ factors, Dyck paths of semilength $n$ , and binary trees on $n$ internal nodes. Their generating function $C (x) = \sum_{n = 0}^{\infty} C_{n} x^{n}$ satisfies $C (x) = 1 + x C (x)^{2}$ , solved by $C (x) = (1 - 1 - 4 x) / (2 x)$ . The binomial-coefficient formula for $C_{n}$ follows by extracting the coefficient of $x^{n}$ from the Taylor expansion of this square root using Newton's generalized theorem.

Theorem 4 (Chu-Vandermonde identity). For non-negative integers $m, n, r$ :

$(r m + n) = k = 0 \sum r (k m) (r - k n) .$

This identity is the convolution rule for binomial coefficients. In probabilistic terms, it states that the number of ways to choose $r$ items from two disjoint pools of sizes $m$ and $n$ equals the sum over all splits $k$ and $r - k$ between the pools. The identity is the coefficient-of- $x^{r}$ reading of $(1 + x)^{m + n} = (1 + x)^{m} (1 + x)^{n}$ .

Theorem 5 (central binomial coefficient asymptotics). The central binomial coefficient $(n 2 n)$ satisfies

$(n 2 n) \sim \frac{4 ^{n}}{π n}$

as $n \to \infty$ , a consequence of Stirling's approximation $n! \sim 2 π n (n / e)^{n}$ . This estimate governs the growth rate of the Catalan numbers $C_{n} \sim 4^{n} / (n^{3/2} π)$ and appears in the analysis of random walks and lattice-path enumeration.

Theorem 6 (multinomial theorem). For a sum of $m$ variables raised to the $n$ -th power:

$(x_{1} + x_{2} + \dots + x_{m})^{n} = k_{1} + k_{2} + \dots + k_{m} = n k_{i} \geq 0 \sum (k _{1} , k _{2} , \dots , k _{m} n) x_{1}^{k_{1}} x_{2}^{k_{2}} \dots x_{m}^{k_{m}},$

where the multinomial coefficient $(k _{1} , \dots , k _{m} n) = n! / (k_{1}! k_{2}! \dots k_{m}!)$ counts the number of ways to distribute $n$ labeled objects into $m$ labeled boxes with $k_{i}$ objects in box $i$ . The binomial theorem is the $m = 2$ case.

Theorem 7 (negated upper index). For non-negative integers $n$ and $k$ :

$(k - n) = (- 1)^{k} (k n + k - 1) .$

This identity connects the generalized binomial coefficient at negative arguments to the ordinary binomial coefficient with a sign alternation. It is the algebraic content behind $(1 - x)^{- n} = \sum_{k = 0}^{\infty} (k n + k - 1) x^{k}$ , the generating function for combinations with repetition.

Synthesis. The binomial theorem is the foundational reason that polynomial multiplication and combinatorial counting coincide, and this is exactly the content of the generating-function interpretation: $(1 + x)^{n}$ encodes the sequence $(k n)$ as its coefficients, and algebraic operations on the polynomial mirror combinatorial operations on the sets. The central insight is that Pascal's recurrence — the addition rule in the triangle — is both the engine of the inductive proof and the algebraic identity that generates every coefficient from the row before. Putting these together with Newton's generalized theorem, the pattern generalises from integer exponents to arbitrary real $α$ , where the finite sum becomes an infinite series and the bridge is the analytic convergence for $∣ x ∣ < 1$ . The binomial theorem appears again in the Catalan-number generating function $C (x) = (1 - 1 - 4 x) / (2 x)$ , where Newton's generalized expansion extracts $C_{n} = \frac{1}{n + 1} (n 2 n)$ , and this identifies the Catalan numbers with the combinatorics of balanced parentheses, Dyck paths, and binary trees. The pattern recurs throughout enumerative combinatorics: every counting sequence with a recursive decomposition has a generating function whose algebraic properties encode the recursion.

Full proof set [Master]

Proposition 1 (alternating row sum). For every positive integer $n$ :

$(0 n) - (1 n) + (2 n) - \dots + (- 1)^{n} (n n) = 0.$

Proof. Set $a = 1, b = - 1$ in the binomial theorem. The left side is $(1 - 1)^{n} = 0$ . The right side is $\sum_{k = 0}^{n} (k n) 1^{n - k} (- 1)^{k} = \sum_{k = 0}^{n} (- 1)^{k} (k n)$ . $□$

Proposition 2 (hockey-stick identity). For $n \geq r \geq 0$ :

$(r r) + (r r + 1) + (r r + 2) + \dots + (r n) = (r + 1 n + 1) .$

Proof. By induction on $n - r$ . Base case: when $n = r$ , both sides equal $(r r) = 1 = (r + 1 r + 1)$ . Inductive step: assume the identity for $n - 1$ :

$i = r \sum n - 1 (r i) = (r + 1 n) .$

Add $(r n)$ to both sides and apply Pascal's recurrence:

$i = r \sum n (r i) = (r + 1 n) + (r n) = (r + 1 n + 1) . □$

Proposition 3 (negated upper index). For non-negative integers $n, k$ :

$(k - n) = (- 1)^{k} (k n + k - 1) .$

Proof. By the generalized binomial coefficient formula:

$(k - n) = \frac{( - n ) ( - n - 1 ) ( - n - 2 ) \dots ( - n - k + 1 )}{k !} .$

Each of the $k$ factors in the numerator contributes a factor of $- 1$ :

$= (- 1)^{k} \cdot \frac{n ( n + 1 ) ( n + 2 ) \dots ( n + k - 1 )}{k !} = (- 1)^{k} \cdot \frac{( n + k - 1 )!}{k ! ( n - 1 )!} = (- 1)^{k} (k n + k - 1) . □$

Connections [Master]

Mathematical induction 00.12.01. The binomial theorem is proved by induction on the exponent $n$ , and the proof is the paradigmatic worked example that motivated Pascal's 1654 Traite du triangle arithmetique ^{[Pascal 1654]} — the same text that introduced mathematical induction as a named technique. Pascal's recurrence, the engine of the inductive step, is the algebraic face of the triangle's addition rule. The binomial theorem builds toward every inductive argument in combinatorics where a recursive decomposition of a counting problem mirrors an algebraic identity.
Polynomials and rational expressions 00.01.03. The binomial theorem is a fundamental identity in the polynomial ring $k [x, y]$ : it expresses $(x + y)^{n}$ as a sum of monomials with explicitly computable coefficients. Every polynomial expansion of a product of binomial factors reduces to repeated application of this identity. The factor theorem from 00.01.03 feeds the binomial theorem in the opposite direction: evaluating the expanded polynomial at $x = - y$ gives zero for $n \geq 1$ , confirming that $x + y$ divides $(x + y)^{n}$ in $k [x, y]$ .
Real numbers, integers, rationals 00.01.01. The binomial coefficients $(k n) = n! / (k! (n - k)!)$ are integers, even though the formula involves division of factorials. This integrality — a consequence of the combinatorial interpretation or of the product formula $(k n) = (n / k) (k - 1 n - 1)$ with inductive descent to $k = 0$ — is a structural property of the integers $Z$ that would fail in a general ring. The Catalan numbers $C_{n} = \frac{1}{n + 1} (n 2 n)$ are likewise integers, a deeper integrality result that requires the combinatorial interpretation.

Historical & philosophical context [Master]

Pascal 1654 Traite du triangle arithmetique ^{[Pascal 1654]} gave the first systematic treatment of the arithmetic triangle, including Pascal's recurrence, the combinatorial interpretation of the entries as "the number of ways to choose," and the earliest explicit proof by mathematical induction applied to the properties of the triangle. Earlier appearances of the triangle include Halayudha's commentary on Pingala's Chandahshastra (~~10th century, India), al-Karaji's al-Fakhri (~~1000 CE, Baghdad), and Yang Hui's account in China (1261), but Pascal's treatment unified the triangle's properties with a coherent proof framework and the inductive method.

Newton 1665–1666 De analysi per aequationes numero terminorum infinitas ^{[Newton 1665]} extended the binomial theorem to fractional and negative exponents by treating $(1 + x)^{1/2}$ as an infinite series $1 + \frac{1}{2} x - \frac{1}{8} x^{2} + \dots$ and verifying the expansion by squaring. Newton's insight was that the pattern of the integer-exponent binomial coefficients persists when the exponent is any rational number, with the series becoming infinite. The convergence proof for the generalized binomial series was completed by Abel 1826 ^{[Abel 1826]}, who established the radius of convergence $∣ x ∣ < 1$ using techniques that anticipate modern analysis.

Bibliography [Master]

@article{Pascal1654,
  author = {Pascal, Blaise},
  title = {Trait\'{e} du triangle arithm\'{e}tique},
  year = {1654},
  note = {Published posthumously 1665, Paris}
}

@book{Newton1665,
  author = {Newton, Isaac},
  title = {De analysi per aequationes numero terminorum infinitas},
  year = {1665},
  note = {Written 1665--1666; published 1711, London}
}

@article{Abel1826,
  author = {Abel, Niels Henrik},
  title = {Untersuchungen \"{u}ber die Reihe $1 + \frac{m}{1}x + \frac{m(m-1)}{1 \cdot 2}x^2 + \cdots$ u.s.w.},
  journal = {Journal f\"{u}r die reine und angewandte Mathematik},
  volume = {1},
  pages = {311--339},
  year = {1826}
}

@book{StanleyEC1,
  author = {Stanley, Richard P.},
  title = {Enumerative Combinatorics, Volume 1},
  publisher = {Cambridge University Press},
  year = {2012},
  edition = {2nd}
}

@book{GrahamKnuthPatashnik,
  author = {Graham, Ronald L. and Knuth, Donald E. and Patashnik, Oren},
  title = {Concrete Mathematics},
  publisher = {Addison-Wesley},
  year = {1994},
  edition = {2nd}
}

Prerequisites

00.12.01
00.01.01

Tier anchors

beginner: Lang Basic Mathematics Ch. 1; Pascal's triangle as a number pattern
intermediate: Apostol Calculus Vol. 1 Ch. 1; Lang Basic Mathematics Ch. 1
master: Pascal 1654 Traite du triangle arithmetique; Newton 1665 De analysi; Stanley Enumerative Combinatorics Vol. 1

References

TODO_REF
Pascal — Traite du triangle arithmetique · 1654, the arithmetic triangle and its properties
TODO_REF
Newton — De analysi per aequationes numero terminorum infinitas · 1665-1666, generalized binomial theorem
TODO_REF
Abel — Untersuchungen uber die Reihe · 1826, J. Reine Angew. Math. 1, convergence of the binomial series
TODO_REF
Lang — Basic Mathematics · Ch. 1, binomial coefficients
TODO_REF
Apostol — Calculus Vol. 1 · Ch. 1, mathematical induction and the binomial theorem
TODO_REF
Stanley — Enumerative Combinatorics Vol. 1 · Ch. 1, binomial coefficients and generating functions

Reviewer

TBD

Estimated time

beginner: 15m
intermediate: 35m
master: 70m