Binomial Theorem

Definition and Statement

Binomial Expression

Expression: (a + b)^n, where n ∈ ℕ_0, a,b ∈ ℝ or ℂ. Objective: expand into sum of terms involving powers of a and b.

Binomial Theorem

Statement: (a + b)^n = Σ_{k=0}^n (n choose k) a^{n-k} b^k. Coefficients: binomial coefficients, combinatorial counts.

Notation and Terminology

Notation: Σ denotes sum, (n choose k) = C(n,k) = n! / (k! (n-k)!). Terms: binomial expansion, coefficients.

"Mathematics is the art of giving the same name to different things." -- Henri Poincaré

Binomial Coefficients

Definition

Formula: C(n,k) = n!/(k!(n-k)!), counts k-element subsets of n-element set. Domain: 0 ≤ k ≤ n.

Properties

Symmetry: C(n,k) = C(n,n-k). Boundary values: C(n,0) = C(n,n) = 1. Pascal's rule: C(n,k) = C(n-1,k-1) + C(n-1,k).

Computational Methods

Direct factorial calculation: costly for large n. Recursion: dynamic programming. Multiplicative formula: product-based computation.

Pascal's Triangle

Construction

Triangle of numbers with rows indexed from 0. Each entry: sum of two above entries. Top row: 1.

Relation to Binomial Coefficients

Row n contains binomial coefficients C(n,0), C(n,1), ..., C(n,n). Visual and computational aid.

Applications

Quick lookup of coefficients. Basis for combinatorial identities and recursive algorithms.

Proofs of the Theorem

Combinatorial Proof

Interpretation: number of ways to select k b's out of n factors. Sum over k yields expansion.

Inductive Proof

Base case: n=0, (a+b)^0=1. Inductive step: multiply (a+b)^n by (a+b), apply distributive law, use Pascal’s rule.

Algebraic Proof Using Generating Functions

Expand (1+x)^n via power series, equate coefficients with binomial coefficients.

Base case: (a+b)^0 = 1Assume (a+b)^n = Σ C(n,k) a^{n-k} b^kThen (a+b)^{n+1} = (a+b)(a+b)^n= a Σ C(n,k) a^{n-k} b^k + b Σ C(n,k) a^{n-k} b^k= Σ C(n,k) a^{n+1-k} b^k + Σ C(n,k) a^{n-k} b^{k+1}Re-index second sum: k → k-1Apply Pascal's rule: C(n+1,k) = C(n,k) + C(n,k-1)

Properties of Binomial Coefficients

Symmetry

C(n,k) = C(n,n-k), reflects subset complementarity.

Summation

Sum over k: Σ_{k=0}^n C(n,k) = 2^n, total subsets of n-element set.

Alternating Sum

Σ_{k=0}^n (-1)^k C(n,k) = 0 for n≥1, reflects combinatorial cancellation.

Vandermonde's Identity

Σ_{k=0}^r C(m,k) C(n,r-k) = C(m+n,r), convolution property.

Applications

Algebraic Expansions

Expand polynomials (a+b)^n without repeated multiplication.

Combinatorics

Count subsets, permutations with restrictions, and combinatorial configurations.

Probability Theory

Binomial distributions, modeling success/failure experiments with fixed trials.

Algorithm Design

Efficient computations in recursive algorithms, dynamic programming, and numeric methods.

Generalizations

Multinomial Theorem

Expansion of (x_1 + x_2 + ... + x_m)^n using multinomial coefficients.

Negative and Fractional Powers

Generalized binomial series: infinite series expansion valid for |x|<1, using generalized coefficients.

q-Binomial Theorem

q-analogs of binomial coefficients, related to quantum groups and partitions.

Worked Examples

Example 1: Expand (x + y)^4

Using binomial theorem: Σ_{k=0}^4 C(4,k) x^{4-k} y^k

(x + y)^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4

Example 2: Find coefficient of x^2 y^3 in (x + y)^5

Coefficient: C(5,3) = 10

Example 3: Sum of binomial coefficients for n=5

Σ_{k=0}^5 C(5,k) = 2^5 = 32

Computation Algorithms

Dynamic Programming

Build Pascal's triangle row-by-row, store values to avoid recomputation.

Multiplicative Formula

Compute C(n,k) using product formula to reduce factorial overhead:

C(n,k) = ∏_{i=1}^k (n - i + 1)/i

Recursive Computation

Use Pascal's rule recursively with memoization for efficiency.

Related Identities

Binomial Identity

Sum of powers: Σ_{k=0}^n C(n,k) k = n 2^{n-1}

Chu–Vandermonde Identity

Σ_{k=0}^r C(m,k) C(n,r-k) = C(m+n,r), convolution of coefficients.

Binomial Inversion

Transform between sequences using binomial coefficients.

Connections to Probability

Binomial Distribution

Probability mass function: P(X=k) = C(n,k) p^k (1-p)^{n-k} for k successes in n trials.

Bernoulli Trials

Sequence of n independent experiments, each with success probability p.

Expected Value and Variance

Expected value: np. Variance: np(1-p). Derived using binomial coefficients and expansions.

References

• R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd ed., Addison-Wesley, 1994, pp. 162–180.
• R. P. Stanley, Enumerative Combinatorics, Volume 1, Cambridge University Press, 1997, pp. 45–70.
• G. E. Andrews, K. Eriksson, Integer Partitions, Cambridge University Press, 2004, pp. 15–34.
• W. Feller, An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd ed., Wiley, 1968, pp. 156–160.
• D. M. Burton, Elementary Number Theory, 7th ed., McGraw-Hill, 2010, pp. 123–135.