26-04 — Binomial Theorem (Combinatorics Focus)

Phase: Combinatorics | Subject: 26-04 Prerequisites: 26-03-combinations.md, 03-09-binomial-theorem.md (optional review) Next subject: 26-05-pigeonhole-principle.md

Learning Objectives

By the end of this subject, you will be able to:

1. Prove the binomial theorem using combinatorial reasoning
2. Derive identities from the binomial theorem: $\sum_k \binom{n}{k} = 2^n$, $\sum_k (-1)^k \binom{n}{k} = 0$
3. Apply the multinomial theorem
4. Use generating function interpretation of binomial expansions
5. Solve advanced binomial coefficient identities

Core Content

Combinatorial Proof of the Binomial Theorem

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

Combinatorial argument: Expand $(x+y)(x+y)\cdots(x+y)$ ($n$ factors). Each term is formed by choosing $x$ from some factors and $y$ from the others. The coefficient of $x^{n-k}y^k$ is the number of ways to choose which $k$ factors contribute $y$ — that's $\binom{n}{k}$.

Identities from the Binomial Theorem

Set $x = y = 1$: $$\sum_{k=0}^{n} \binom{n}{k} = 2^n$$

Set $x = 1, y = -1$: $$\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0$$

Set $x = 1, y = 2$: $$\sum_{k=0}^{n} \binom{n}{k} 2^k = 3^n$$

Each choice of $x$ and $y$ yields a new identity.

Vandermonde's Identity

$$\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k} \binom{n}{r-k}$$

Combinatorial proof: Choose $r$ people from $m$ men and $n$ women. Count by cases: pick $k$ men ($\binom{m}{k}$) and $r-k$ women ($\binom{n}{r-k}$), sum over all $k$.

Hockey-Stick Identity

$$\sum_{k=r}^{n} \binom{k}{r} = \binom{n+1}{r+1}$$

Combinatorial proof: Among all $(r+1)$-subsets of ${0, 1, \ldots, n}$, group by the largest element.

The Multinomial Theorem

$$(x_1 + x_2 + \cdots + x_m)^n = \sum_{k_1 + \cdots + k_m = n} \frac{n!}{k_1! k_2! \cdots k_m!} x_1^{k_1} x_2^{k_2} \cdots x_m^{k_m}$$

The multinomial coefficient $\frac{n!}{k_1! \cdots k_m!}$ counts the number of ways to arrange $n$ objects where $k_i$ are of type $i$.

Example: Find coefficient of $x^2 y^3 z$ in $(x + y + z)^6$. $\frac{6!}{2! 3! 1!} = \frac{720}{2 \times 6 \times 1} = 60$.

Key Terms

• Binomial Theorem
• Vandermonde's Identity
• Hockey-Stick Identity
• Multinomial Theorem

Worked Examples

Example 1: Identity from the Binomial Theorem

Prove $\sum_{k=0}^{n} k\binom{n}{k} = n 2^{n-1}$.

Solution: Method 1 (combinatorial): Count committees of any size with a designated chair. Choose chair ($n$ ways), then choose any subset of the remaining $n-1$ members ($2^{n-1}$ ways). This equals counting by size: for each size $k$, choose the $k$ members ($\binom{n}{k}$) then a chair ($k$ ways).

Method 2 (analytic): Differentiate $(1+x)^n = \sum \binom{n}{k}x^k$, set $x=1$: $n(1+x)^{n-1}|_{x=1} = \sum k\binom{n}{k} \Rightarrow n2^{n-1} = \sum k\binom{n}{k}$.

Example 2: Vandermonde Application

Prove $\binom{2n}{n} = \sum_{k=0}^{n} \binom{n}{k}^2$.

Solution: By Vandermonde with $m = n$: $\binom{2n}{n} = \sum_{k=0}^{n} \binom{n}{k}\binom{n}{n-k} = \sum_{k=0}^{n} \binom{n}{k}^2$ (by symmetry).

Example 3: Multinomial Coefficients

How many distinct arrangements of "SUCCESS"?

Solution: 7 letters: S=3, C=2, U=1, E=1. $\frac{7!}{3! 2! 1! 1!} = \frac{5040}{12} = 420$.

Quiz

Q1: What does the concept of Binomial Theorem primarily refer to in this subject?

A) A computational error related to Binomial Theorem B) A historical anecdote about Binomial Theorem C) The definition and application of Binomial Theorem D) A visual representation of Binomial Theorem

Correct: C)

• If you chose A: This is incorrect. Binomial Theorem is defined as: the definition and application of binomial theorem. The other options describe different aspects that are not the primary focus.
• If you chose B: This is incorrect. Binomial Theorem is defined as: the definition and application of binomial theorem. The other options describe different aspects that are not the primary focus.
• If you chose C: Binomial Theorem is defined as: the definition and application of binomial theorem. The other options describe different aspects that are not the primary focus. Correct!
• If you chose D: This is incorrect. Binomial Theorem is defined as: the definition and application of binomial theorem. The other options describe different aspects that are not the primary focus.

Q2: Which of the following is the key formula discussed in this subject?

A) \sum_k \binom{n}{k} = 2^n B) A simplified version of \sum_k \binom{n}{k} = 2^n... C) The inverse operation of the formula in question D) An unrelated formula from a different topic

Correct: A)

• If you chose A: The formula \sum_k \binom{n}{k} = 2^n is central to this subject. The other options are either simplified versions or unrelated. Correct!
• If you chose B: This is incorrect. The formula \sum_k \binom{n}{k} = 2^n is central to this subject. The other options are either simplified versions or unrelated.
• If you chose C: This is incorrect. The formula \sum_k \binom{n}{k} = 2^n is central to this subject. The other options are either simplified versions or unrelated.
• If you chose D: This is incorrect. The formula \sum_k \binom{n}{k} = 2^n is central to this subject. The other options are either simplified versions or unrelated.

Q3: What is the primary purpose of Hockey-Stick Identity?

A) It replaces all other methods in this domain B) It is used only in advanced research contexts C) It is primarily a historical notation system D) It is used to hockey-stick identity in mathematical analysis

Correct: D)

• If you chose A: This is incorrect. Hockey-Stick Identity serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose B: This is incorrect. Hockey-Stick Identity serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose C: This is incorrect. Hockey-Stick Identity serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose D: Hockey-Stick Identity serves the purpose described in the correct answer. The other options misrepresent its role. Correct!

Q4: Which statement about Multinomial Theorem is TRUE?

A) Multinomial Theorem is an advanced topic beyond this subject's scope B) Multinomial Theorem is not related to this subject C) Multinomial Theorem is a fundamental concept covered in this subject D) Multinomial Theorem is mentioned only as a historical footnote

Correct: C)

• If you chose A: This is incorrect. Multinomial Theorem is a fundamental concept covered in this subject. This subject covers Multinomial Theorem as part of its core content.
• If you chose B: This is incorrect. Multinomial Theorem is a fundamental concept covered in this subject. This subject covers Multinomial Theorem as part of its core content.
• If you chose C: Multinomial Theorem is a fundamental concept covered in this subject. This subject covers Multinomial Theorem as part of its core content. Correct!
• If you chose D: This is incorrect. Multinomial Theorem is a fundamental concept covered in this subject. This subject covers Multinomial Theorem as part of its core content.

Q5: Based on the worked examples in this subject, what is the correct result?

A) The inverse of the correct answer B) An unrelated numerical value C) A different result from a common mistake D) Vandermonde Application

Correct: D)

• If you chose A: This is incorrect. The worked examples show that the result is Vandermonde Application. The other options represent common errors.
• If you chose B: This is incorrect. The worked examples show that the result is Vandermonde Application. The other options represent common errors.
• If you chose C: This is incorrect. The worked examples show that the result is Vandermonde Application. The other options represent common errors.
• If you chose D: The worked examples show that the result is Vandermonde Application. The other options represent common errors. Correct!

Q6: How are Multinomial Theorem and Combinatorial Proof Of The Binomial Theorem related?

A) Multinomial Theorem is the inverse of Combinatorial Proof Of The Binomial Theorem B) Multinomial Theorem and Combinatorial Proof Of The Binomial Theorem are closely related concepts C) Multinomial Theorem is a special case of Combinatorial Proof Of The Binomial Theorem D) Multinomial Theorem and Combinatorial Proof Of The Binomial Theorem are completely unrelated topics

Correct: B)

• If you chose A: This is incorrect. Both Multinomial Theorem and Combinatorial Proof Of The Binomial Theorem are covered in this subject as interconnected topics.
• If you chose B: Both Multinomial Theorem and Combinatorial Proof Of The Binomial Theorem are covered in this subject as interconnected topics. Correct!
• If you chose C: This is incorrect. Both Multinomial Theorem and Combinatorial Proof Of The Binomial Theorem are covered in this subject as interconnected topics.
• If you chose D: This is incorrect. Both Multinomial Theorem and Combinatorial Proof Of The Binomial Theorem are covered in this subject as interconnected topics.

Q7: What is a common pitfall when working with Identities From The Binomial Theorem?

A) The main error with Identities From The Binomial Theorem is using it when it is not needed B) Identities From The Binomial Theorem is always computed the same way in all contexts C) Identities From The Binomial Theorem has no common misconceptions D) A common mistake is confusing Identities From The Binomial Theorem with a similar concept

Correct: D)

• If you chose A: This is incorrect. Students often confuse Identities From The Binomial Theorem with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose B: This is incorrect. Students often confuse Identities From The Binomial Theorem with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose C: This is incorrect. Students often confuse Identities From The Binomial Theorem with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose D: Students often confuse Identities From The Binomial Theorem with similar-sounding or related concepts. Pay attention to the precise definitions. Correct!

Q8: When should you apply Vandermonde'S Identity?

A) Avoid Vandermonde'S Identity unless explicitly instructed B) Apply Vandermonde'S Identity to solve problems in this subject's domain C) Use Vandermonde'S Identity only in pure mathematics contexts D) Vandermonde'S Identity is not practically useful

Correct: B)

• If you chose A: This is incorrect. Vandermonde'S Identity is a practical tool used throughout this subject to solve relevant problems.
• If you chose B: Vandermonde'S Identity is a practical tool used throughout this subject to solve relevant problems. Correct!
• If you chose C: This is incorrect. Vandermonde'S Identity is a practical tool used throughout this subject to solve relevant problems.
• If you chose D: This is incorrect. Vandermonde'S Identity is a practical tool used throughout this subject to solve relevant problems.

Practice Problems

1. Expand $(2x - 3y)^4$ using the binomial theorem.
   

   Click for answer

   $\binom{4}{0}(2x)^4 + \binom{4}{1}(2x)^3(-3y) + \binom{4}{2}(2x)^2(-3y)^2 + \binom{4}{3}(2x)(-3y)^3 + \binom{4}{4}(-3y)^4 = 16x^4 - 96x^3y + 216x^2y^2 - 216xy^3 + 81y^4$.

2. Prove $\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$.
   

   Click for answer

   Vandermonde: $\binom{n+n}{n} = \sum_k \binom{n}{k}\binom{n}{n-k} = \sum_k \binom{n}{k}^2$.

3. Find the coefficient of $x^3 y^4 z^5$ in $(x+y+z)^{12}$.
   

   Click for answer

   $\frac{12!}{3!4!5!} = \frac{479,001,600}{6 \times 24 \times 120} = 27,720$.

4. Evaluate $\sum_{k=0}^{10} \binom{10}{k} 3^k$.
   

   Click for answer

   $(1+3)^{10} = 4^{10} = 1,048,576$.

5. What identity follows from $(1+x)^n(1+x)^m = (1+x)^{m+n}$?
   

   Click for answer

   Comparing coefficient of $x^r$: $\sum_k \binom{n}{k}\binom{m}{r-k} = \binom{m+n}{r}$ — Vandermonde's Identity.

Summary

Key takeaways:

• Binomial theorem: $(x+y)^n = \sum \binom{n}{k} x^{n-k} y^k$ — combinatorially, choose which $k$ factors give $y$
• Plugging in $x,y$ values generates binomial identities
• Vandermonde: $\binom{m+n}{r} = \sum \binom{m}{k}\binom{n}{r-k}$
• Hockey-stick: $\sum_{k=r}^n \binom{k}{r} = \binom{n+1}{r+1}$
• Multinomial theorem generalizes to more than two variables

Pitfalls

• Forgetting the combinatorial interpretation of $\binom{n}{k}$ in the binomial theorem: The coefficient $\binom{n}{k}$ in $(x+y)^n = \sum \binom{n}{k} x^{n-k} y^k$ counts the number of ways to choose which $k$ factors contribute $y$. Students who memorize the expansion pattern without this interpretation struggle to generalize — the multinomial theorem, Vandermonde's identity, and generating function derivations all flow from the combinatorial "choose which factors" insight.
• Misapplying Vandermonde's identity by getting the indices wrong: Vandermonde states $\binom{m+n}{r} = \sum_{k=0}^r \binom{m}{k}\binom{n}{r-k}$. A common mistake is summing over the wrong range (e.g., $k$ from 0 to $m$ instead of 0 to $r$) or swapping $m$ and $n$ in the terms. The identity counts choosing $r$ items from two disjoint groups — the sum over $k$ (items from group 1) naturally stops at $\min(r, m)$.
• Confusing multinomial coefficients with binomial coefficients: The multinomial coefficient $\frac{n!}{k_1! k_2! \cdots k_m!}$ counts arrangements of $n$ objects with $k_i$ of type $i$, while $\binom{n}{k}$ counts selections. A frequent error: using $\binom{6}{2,2,2}$ notation without realizing this equals $\frac{6!}{2!2!2!} = 90$, not $\binom{6}{2} = 15$. The multinomial coefficient is always larger than any of its constituent binomial coefficients because it accounts for multiple object types simultaneously.
• Ignoring signs when substituting $y = -1$ or negative values: $(x - y)^n = \sum \binom{n}{k} x^{n-k} (-y)^k = \sum (-1)^k \binom{n}{k} x^{n-k} y^k$. The $(-1)^k$ factor alternates signs. When deriving identities by plugging in values like $x=1, y=-1$, forgetting the sign pattern leads to incorrect sums. Always write the full term including the sign before simplifying.
• Deriving identities by differentiating the binomial theorem without checking convergence: Differentiating $(1+x)^n = \sum \binom{n}{k} x^k$ is valid for finite $n$ (polynomial), but for infinite series (negative or non-integer $n$) the power series representation $\sum \binom{n}{k}x^k$ converges only for $|x| < 1$ and termwise differentiation must be justified. When working with generating functions later, keep convergence radius in mind.

Next Steps

Next up: 26-05-pigeonhole-principle.md — a deceptively simple but powerful existence principle.