Binomial Theorem from a Combinatorial Perspective

The binomial theorem describes how to expand a binomial expression of the form $(x + y)^n$. The following provides a detailed explanation of its proof through the lens of combinatorics, transforming abstract algebraic expansion into a concrete counting problem.

Statement of the Binomial Theorem

For any nonnegative integer $n$, we have:

$$(x + y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k} y^k$$

where $\binom{n}{k}$ is the binomial coefficient (the number of ways to choose $k$ from $n$), defined as:

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

Core Idea of the Combinatorial Proof

Core idea: Consider the expansion of $(x + y)^n$ as selecting $x$ or $y$ from each of the $n$ factors $(x + y)$, interpreting the coefficients as the number of ways to choose $y$ from $n$ factors.

Detailed Expansion Process

1. Product structure:
   View $(x + y)^n$ as the product of $n$ factors $(x + y)$:
   $(x + y)^n = (x + y)(x + y)\cdots(x + y) \quad (\text{total } n \text{ factors})$

2. Generating terms:
   Each term in the expansion has the form $x^{n-k} y^k$, generated by choosing $k$ factors from which to take $y$ and taking $x$ from the remaining $n-k$ factors. For example:

   • When $n=3$, the term $x^2 y$ arises by choosing 1 factor to take $y$ from 3 factors, and taking $x$ from the other two. There are $\binom{3}{1}=3$ ways to do this.

3. Correspondence between coefficients and binomial coefficients:
   The coefficient of each term $x^{n-k} y^k$ equals the number of ways to choose $k$ $y$‘s, i.e., $\binom{n}{k}$. For example:

   • The coefficient of $xy^2$ in $(x + y)^3$ is $\binom{3}{2}=3$, corresponding to the three ways of choosing two factors to take $y$: $(y,y,x)$, $(y,x,y)$, $(x,y,y)$.

Formal Mathematical Proof

1. Analysis of term generation:
   All possible terms in the expansion arise from the following selection process:

   • From each factor $(x + y)$, choose either $x$ or $y$.
   • Multiply the selected results from each factor, obtaining a term of the form $x^{n-k} y^k$.

2. Role of binomial coefficients:
   The number of ways to choose $k$ factors to take $y$ is $\binom{n}{k}$, so the coefficient of $x^{n-k} y^k$ is $\binom{n}{k}$. Summing over all possible $k$ ($0 \leq k \leq n$) gives the complete expansion.

Example Verification

Take $n=4$ as an example:

$$(x + y)^4 = \binom{4}{0}x^4 + \binom{4}{1}x^3 y + \binom{4}{2}x^2 y^2 + \binom{4}{3}x y^3 + \binom{4}{4}y^4$$

Expanding yields:

$$x^4 + 4x^3 y + 6x^2 y^2 + 4x y^3 + y^4$$

where the coefficients $\{1,4,6,4,1\}$ exactly correspond to the binomial coefficients $\binom{4}{k}$, verifying the theorem.