A Combinatorial Derivation of the Binomial Theorem

1. Basic Counting Principles and Notation

Before deriving complex formulas, we must establish our fundamental objects and counting rules.

a. Definitions

1. Finite Set: A collection of distinct objects with a specific number of elements.
2. Cardinality: The number of elements in a set $S$, denoted as $|S|$.
3. Subset: Set $A$ is a subset of $B$ (denoted $A \subseteq B$) if every element of $A$ is also in $B$.
4. Factorial ($n!$): For a non-negative integer $n$, $n!$ is the product of all positive integers less than or equal to $n$. By convention, $0! = 1$. $$n! = n \times (n-1) \times \dots \times 2 \times 1$$
5. Permutation: An ordered arrangement of objects.

b. Permutations of $n$ Distinct Objects

Theorem: The number of ways to arrange $n$ distinct objects in a line is $n!$.

Proof: We use the Multiplication Principle (or the "Slot Method"). Imagine we have $n$ distinct objects and $n$ empty slots to fill in a linear order.

• First Slot: We can choose any of the $n$ objects. There are $n$ choices.
• Second Slot: We have already used one object. There are $n-1$ objects remaining. Thus, there are $n-1$ choices.
• Third Slot: There are $n-2$ objects remaining.
• ...
• Last Slot: There is only 1 object left.

By the Multiplication Principle, the total number of distinct arrangements is the product of the choices at each step:

2. First Principles Derivation of Combinations

a. Definition of Binomial Coefficients

We define the symbol $\binom{n}{k}$ (read "n choose k") as the number of subsets of size $k$ that can be formed from a set of $n$ distinct elements. Crucially, in a subset, order does not matter.

The same quantity is written in several equivalent ways. You will encounter $\binom{n}{k}$, $\,{}_nC_k$, $\,nCk$, and $C(n,k)$ across different textbooks and calculators—these are all notations for the same number.

b. Deriving the Formula

Theorem: For $0 \le k \le n$:

Proof (The Ordered vs. Unordered Argument): We will count the number of ordered selections of size $k$ from a set of size $n$ in two different ways. Let this count be $N$.

Since both methods count the same set of outcomes $N$, we equate them:

3. Key Combinatorial Identities

We now prove standard identities using combinatorial proof (counting stories), not algebra.

a. Symmetry Identity

Combinatorial Proof: Let $S$ be a set of $n$ people. We want to form a committee of $k$ people.

• LHS ($\binom{n}{k}$): Count the number of ways to choose $k$ people to be on the committee.
• RHS ($\binom{n}{n-k}$): Alternatively, we can choose the committee by deciding who is left out. If we choose $n-k$ people to reject, the remaining $k$ people automatically form the committee.

Conclusion: There is a one-to-one correspondence (bijection) between a subset of size $k$ and its complement of size $n-k$.

b. Pascal's Identity

Combinatorial Proof: Let $S$ be a set of $n+1$ people. We want to choose a team of size $k$. Let one specific person in the set be named "Alice". We partition all possible teams into two mutually exclusive cases:

Conclusion: By the Addition Rule (Sum Rule), the total ways to choose the team is the sum of these two cases.

c. Sum of a Row

Combinatorial Proof: We want to count the total number of possible subsets of a set $S$ with $n$ elements (i.e., the size of the Power Set).

• LHS ($\sum \binom{n}{k}$): We can group the subsets by their size. (Size 0 + Size 1 + ... + Size $n$).
• RHS ($2^n$): Alternatively, we can construct a subset by making a binary decision for each of the $n$ elements: is this element in the subset? (2 choices × 2 choices... $n$ times).

4. Combinatorial Interpretation of $(x+y)^n$

To prove the Binomial Theorem, we must understand what the expansion of a product means combinatorially.

a. The Expansion Process

Consider the expression:

To expand this product, the distributive property tells us that we must take a term from the first factor, a term from the second factor, ..., and a term from the $n$-th factor, multiply them together, and do this for all possible combinations of choices.

Since each of the $n$ factors offers a choice of either $x$ or $y$, every resulting term in the expansion looks like $x \cdot y \cdot x \cdot x \cdot \dots \cdot y$. If we choose $y$ exactly $k$ times, we must have chosen $x$ exactly $n-k$ times. This results in a term of the form $x^{n-k}y^k$.

b. The Coefficient as a Subset Selection

For a fixed $k$, how many times does the term $x^{n-k}y^k$ appear in the raw expansion?

To generate a term $x^{n-k}y^k$:

1. We have $n$ distinct factors (brackets).
2. We need to choose exactly $k$ of these brackets to contribute a $y$.
3. The remaining $n-k$ brackets will strictly contribute an $x$.

This is equivalent to the combinatorial problem: "In how many ways can we choose a subset of $k$ indices from the set $\{1, 2, \dots, n\}$?" By definition (Section 2a), the number of ways to choose these $k$ brackets is $\binom{n}{k}$.

5. Combinatorial Proof of the Binomial Theorem

Theorem: For any integer $n \ge 0$:

Proof:

1. Total Expansion: The expansion of $(x+y)^n$ consists of the sum of all possible products formed by picking one variable ($x$ or $y$) from each of the $n$ factors.
2. Grouping Terms: We group these products based on the number of $y$'s selected. The number of $y$'s, denoted by $k$, can range from $0$ to $n$.
3. Form of Terms: For a specific $k$, the term involves multiplying $k$ $y$'s and $(n-k)$ $x$'s, resulting in $x^{n-k}y^k$.
4. Counting Coefficients: As established in Section 4, the number of times the term $x^{n-k}y^k$ is generated is equal to the number of ways to choose which $k$ factors contribute a $y$. This count is $\binom{n}{k}$.
5. Summation: Summing over all possible values of $k$ (from 0 to $n$), we get: $$(x+y)^n = \binom{n}{0}x^ny^0 + \binom{n}{1}x^{n-1}y^1 + \dots + \binom{n}{n}x^0y^n$$ $$(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k}y^k$$

Q.E.D.

6. Optional: Connecting Back to Identities

We can verify our theorem by setting $x=1$ and $y=1$.

$$(1+1)^n = \sum_{k=0}^n \binom{n}{k} (1)^{n-k}(1)^k$$ $$2^n = \sum_{k=0}^n \binom{n}{k}$$

This perfectly recovers the Sum of a Row Identity proved in Section 3c. The algebraic result matches the combinatorial "subset counting" result, confirming the internal consistency of the theory.

7. Concrete Numerical Examples

Example 1: Expanding $(x+y)^3$

Using the theorem for $n=3$:

Calculating the coefficients combinatorially:

• $\binom{3}{0}$: Ways to choose 0 $y$'s from 3 brackets. Only 1 way (choose none).
• $\binom{3}{1}$: Ways to choose 1 $y$ from 3 brackets. 3 ways ($\{1\}, \{2\}, \{3\}$).
• $\binom{3}{2}$: Ways to choose 2 $y$'s from 3 brackets. 3 ways ($\{1,2\}, \{1,3\}, \{2,3\}$).
• $\binom{3}{3}$: Ways to choose 3 $y$'s from 3 brackets. 1 way (choose all).

Result:

Example 2: Selecting a Pizza Topping Combination

Imagine a pizza place offers 4 distinct toppings: {Pepperoni, Mushroom, Onion, Sausage}. You want to analyze the distribution of possible pizzas based on the number of toppings ($n=4$).

8. The Alternating Case: $(x-y)^n$

A binomial is simply a polynomial with two terms, so $x-y$ is still a binomial. The theorem applies unchanged once we replace $y$ with $-y$:

The binomial coefficients are identical to the $(x+y)^n$ case. The only change is the sign: each chosen $-y$ contributes a factor of $-1$, so the term with $k$ copies of $y$ carries the factor $(-1)^k$. The signs therefore alternate $+, -, +, -, \dots$ as $k$ increases.

Example: Expanding $(x-y)^3$ keeps the coefficients $1, 3, 3, 1$:

Compare with $(x+y)^3 = x^3 + 3x^2y + 3xy^2 + y^3$ from Section 7: the magnitudes match exactly; only the odd-power-of-$y$ terms flip sign.

9. Common Misunderstandings

A few recurring errors are worth flagging explicitly.

10. Practice Problems

Work these through to connect the counting, recursion, and algebra viewpoints.

1. Compute $\binom{6}{2}$ using the factorial formula, then interpret the answer as a subset count.
2. Prove $\binom{6}{2} = \binom{6}{4}$ by explaining the symmetry between the chosen and the unchosen elements (Section 3a).
3. Use Pascal's Identity to compute $\binom{7}{3}$ from entries in the previous row ($\binom{6}{2}$ and $\binom{6}{3}$).
4. Explain why the coefficient of $x^2y^3$ in $(x+y)^5$ is $\binom{5}{3}$.
5. Expand $(x-y)^4$ and explain where the alternating signs come from.

11. Solutions to Practice Problems

Worked solutions to the five problems in Section 10.

1. Compute $\binom{6}{2}$ using the factorial formula, then interpret the answer as a subset count.

   Applying $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ with $n=6$, $k=2$:

   $$\binom{6}{2} = \frac{6!}{2!\,4!} = \frac{720}{2 \times 24} = \frac{720}{48} = 15$$

   Interpretation: there are exactly $15$ different two-element subsets of a six-element set—for example, the number of ways to pick a pair of representatives from a group of six people.

2. Prove $\binom{6}{2} = \binom{6}{4}$ by explaining the symmetry between the chosen and the unchosen elements.

   Direct computation confirms the equality:

   $$\binom{6}{2} = \frac{6!}{2!\,4!} = 15, \qquad \binom{6}{4} = \frac{6!}{4!\,2!} = 15$$

   Combinatorial reason (Section 3a): every time we choose the $2$ elements to include, we simultaneously determine the $4$ elements left out. This pairing is a bijection between the size-$2$ subsets and their size-$4$ complements, so the two collections have the same size. In general $\binom{n}{k} = \binom{n}{n-k}$; here $k=2$ and $n-k=4$.

3. Use Pascal's Identity to compute $\binom{7}{3}$ from entries in the previous row ($\binom{6}{2}$ and $\binom{6}{3}$).

   Pascal's Identity (Section 3b) in the form $\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}$ with $n=6$, $k=3$ gives:

   $$\binom{7}{3} = \binom{6}{3} + \binom{6}{2}$$

   Computing the two row-6 entries:

   $$\binom{6}{3} = \frac{6!}{3!\,3!} = 20, \qquad \binom{6}{2} = 15$$

   Therefore:

   $$\binom{7}{3} = 20 + 15 = 35$$

4. Explain why the coefficient of $x^2y^3$ in $(x+y)^5$ is $\binom{5}{3}$.

   Expanding $(x+y)^5 = (x+y)(x+y)(x+y)(x+y)(x+y)$ means choosing either $x$ or $y$ from each of the $5$ factors. A term equals $x^2y^3$ precisely when exactly $3$ of the $5$ factors contribute a $y$ (the remaining $2$ then contribute $x$). The number of ways to choose which $3$ of the $5$ factors supply the $y$ is, by definition, $\binom{5}{3}$. Hence that is the coefficient:

   $$\binom{5}{3} = \frac{5!}{3!\,2!} = 10 \quad\Longrightarrow\quad \text{the term is } 10\,x^2y^3.$$

   This matches the Binomial Theorem term $\binom{n}{k}x^{n-k}y^k$ with $n=5$, $k=3$.

5. Expand $(x-y)^4$ and explain where the alternating signs come from.

   Using the alternating form from Section 8 with $n=4$:

   $$(x-y)^4 = \sum_{k=0}^{4} (-1)^k \binom{4}{k} x^{4-k} y^k$$

   The coefficients $\binom{4}{k}$ are $1, 4, 6, 4, 1$, so:

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

   Where the signs come from: writing $x-y$ as $x+(-y)$, each factor that contributes the second term contributes $-y$, i.e. a factor of $-1$. A term with $k$ copies of $y$ therefore carries $(-1)^k$. The sign is $+$ when $k$ is even ($k=0,2,4$) and $-$ when $k$ is odd ($k=1,3$), producing the alternating $+,-,+,-,+$ pattern.