Day 50 — Binomial theorem & identities

Day 50 — Binomial theorem & identities

Stage V · concept day
Goal: Prove and apply the binomial theorem; master Pascal’s identity and core binomial coefficient identities; meet Catalan numbers with 2–3 combinatorial interpretations (lite).

Why this matters

The binomial theorem is the algebraic twin of subset counting. Identities like \(\sum_k\binom{n}{k}=2^n\) and \(\sum_k k\binom{n}{k}=n2^{n-1}\) appear in algorithm analysis, expected values (Stage VIII), and closed forms for combinatorial sums. Catalan numbers count Dyck words, balanced parentheses, and binary trees—structures you will meet in parsing and data structures. Story proofs + algebraic proofs reinforce each other (Day 56 deepens story proofs).

Theory

Binomial theorem

For nonnegative integer \(n\) and indeterminates (or numbers) \(x,y\):

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

(equivalently \(\sum_{k}\binom{n}{k}x^{k}y^{n-k}\)).

Combinatorial proof. Expanding \((x+y)(x+y)\cdots(x+y)\) (\(n\) factors), each term picks \(x\) or \(y\) from each factor. A term \(x^{n-k}y^{k}\) arises by choosing \(y\) from exactly \(k\) factors: \(\binom{n}{k}\) ways; the product is \(x^{n-k}y^{k}\).

Algebraic proof (induction on \(n\)). Base \(n=0\): \(1=\binom{0}{0}\). Assume for \(n-1\). Then

\[ (x+y)^n = (x+y)(x+y)^{n-1} = (x+y)\sum_{k=0}^{n-1}\binom{n-1}{k}x^{n-1-k}y^{k}. \]

Collect coefficient of \(x^{n-k}y^{k}\): \(\binom{n-1}{k}+\binom{n-1}{k-1}=\binom{n}{k}\) by Pascal. \(\square\)

Pascal’s identity

\[ \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}\qquad (1\le k\le n). \]

Combinatorial proof. Fix \(x\in S\), \(|S|=n\). Partition \(k\)-subsets of \(S\) into those containing \(x\) and those not:

• not containing \(x\): \(\binom{n-1}{k}\);
• containing \(x\): choose \(k-1\) more from remaining: \(\binom{n-1}{k-1}\).

Algebraic proof.

\[ \binom{n-1}{k}+\binom{n-1}{k-1} = \frac{(n-1)!}{k!(n-1-k)!}+\frac{(n-1)!}{(k-1)!(n-k)!} = \frac{(n-1)!}{(k-1)!(n-1-k)!}\left(\frac{1}{k}+\frac{1}{n-k}\right) = \frac{(n-1)!}{(k-1)!(n-1-k)!}\cdot\frac{n}{k(n-k)} = \frac{n!}{k!(n-k)!}=\binom{n}{k}. \]

Specializations of the binomial theorem

Substitution	Identity
\(x=y=1\)	\(\sum_{k=0}^{n}\binom{n}{k}=2^n\)
\(x=1,y=-1\)	\(\sum_{k=0}^{n}\binom{n}{k}(-1)^k=0\) for \(n>0\)
\(y=1\)	\((x+1)^n=\sum\binom{n}{k}x^{n-k}\)
\(x=y=1\) story	total subsets by size

Story for \(2^n\): each of \(n\) elements in or out of a subset → product \(2^n\); also \(\sum_k\binom{n}{k}\).

Story for alternating sum (\(n>0\)): number of even-sized subsets equals number of odd-sized subsets (\(=2^{n-1}\)). Pairing: fix \(x\); map \(A\mapsto A\triangle\{x\}\) swaps parity. Hence difference is \(0\).

Absorption / committee-chair identity

\[ k\binom{n}{k} = n\binom{n-1}{k-1}\qquad (k\ge 1). \]

Story: choose a committee of \(k\) and a chair in the committee.

• Left: committee then chair: \(\binom{n}{k}\cdot k\).
  
• Right: chair first (\(n\)), then \(k-1\) members from remaining: \(n\binom{n-1}{k-1}\).

Sum of \(k\binom{n}{k}\)

\[ \sum_{k=0}^{n} k\binom{n}{k} = \sum_{k=1}^{n} n\binom{n-1}{k-1} = n\sum_{j=0}^{n-1}\binom{n-1}{j} = n2^{n-1}. \]

Story: from \(n\) people, choose a nonempty? Actually: number of ways to choose a subset and a distinguished element in the subset: pick the element first (\(n\)), then any subset of the rest (\(2^{n-1}\)).

Vandermonde’s identity

\[ \binom{m+n}{r} = \sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}. \]

Story: choose \(r\) people from \(m\) men and \(n\) women; if \(k\) men, then \(r-k\) women.

Hockey-stick identity (statement)

\[ \sum_{i=r}^{n}\binom{i}{r} = \binom{n+1}{r+1}. \]

Story sketch: number of \((r+1)\)-subsets of \(\{1,\ldots,n+1\}\) by maximum element \(i+1\): if max is \(i+1\), choose \(r\) from \(\{1,\ldots,i\}\). Full story proof Day 56.

Pascal’s triangle

Row \(n\): coefficients of \((x+y)^n\). Each interior entry is sum of two above—Pascal identity. Useful for hand expansions and pattern spotting (powers of 2 on row sums).

Multinomial awareness

\((x+y+z)^n\) expands with multinomial coefficients \(\frac{n!}{i!j!k!}\) for \(i+j+k=n\).

Catalan numbers (lite)

The Catalan numbers are

\[ C_n = \frac{1}{n+1}\binom{2n}{n} = \binom{2n}{n}-\binom{2n}{n-1}\qquad (n\ge 0), \]

with \(C_0=1\), \(C_1=1\), \(C_2=2\), \(C_3=5\), \(C_4=14\), \(C_5=42\).

Recurrence: \(C_0=1\) and \(C_{n+1}=\sum_{i=0}^{n} C_i C_{n-i}\) (or \(C_n=\sum_{i=0}^{n-1}C_i C_{n-1-i}\)).

Combinatorial interpretations (3)

1. Dyck words / balanced parentheses. Number of correctly matched parenthesis strings with \(n\) pairs; equivalently lattice paths from \((0,0)\) to \((n,n)\) with steps \(E,N\) that never rise above the diagonal (or never have more \(N\) than \(E\) in any prefix—Ballot theorem special case).

2. Binary trees. Number of full binary trees with \(n+1\) leaves (or plane binary trees with \(n\) internal nodes)—recursive structure: left subtree \(C_i\), right \(C_{n-1-i}\).

3. Noncrossing handshakes / triangulations. Ways to connect \(2n\) people around a table with \(n\) non-intersecting handshakes; or triangulations of a convex \((n+2)\)-gon: \(C_n\).

Why divide by \(n+1\)? Total paths \((0,0)\to(n,n)\): \(\binom{2n}{n}\). The reflection principle subtracts the bad paths (those that touch \(y=x+1\)), leaving \(\frac{1}{n+1}\binom{2n}{n}\). Full reflection proof is optional; remember the formula and interpretations.

Worked examples

Example 1 — Expand

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

Example 2 — Coefficient

Coefficient of \(x^3y^4\) in \((x+y)^7\): \(\binom{7}{4}=35\) (or \(\binom{7}{3}\)).

Example 3 — Evaluate sums

\(\sum_{k=0}^{5}\binom{5}{k}=32\).
\(\sum_{k=0}^{5}(-1)^k\binom{5}{k}=0\).
\(\sum_{k}k\binom{5}{k}=5\cdot 16=80\).

Example 4 — Pascal

\(\binom{10}{4}=\binom{9}{4}+\binom{9}{3}=126+84=210\).

Example 5 — Absorption

\(4\binom{10}{4}=10\binom{9}{3}\): left \(4\cdot 210=840\); right \(10\cdot 84=840\).

Example 6 — Vandermonde

\(\binom{5+3}{4}=\binom{8}{4}=70\);
\(\sum_k\binom{5}{k}\binom{3}{4-k}=\binom{5}{1}\binom{3}{3}+\binom{5}{2}\binom{3}{2}+\binom{5}{3}\binom{3}{1}+\binom{5}{4}\binom{3}{0}=5+30+30+5=70\).

Example 7 — Even/odd subsets

\(n=6\): even-sized subsets \(2^5=32\); odd \(32\); difference \(0\).

Example 8 — Extract from \((1+x)^n\)

Coefficient of \(x^k\) in \((1+x)^n\) is \(\binom{n}{k}\).
Coefficient of \(x^3\) in \((1+x)^{10}\): \(\binom{10}{3}=120\).

Example 9 — \((1-x)^n\)

\((1-x)^n=\sum\binom{n}{k}(-1)^k x^k\).
Sum of coefficients: \((1-1)^n=0\) for \(n>0\).

Example 10 — Catalan compute

\(C_4=\frac{1}{5}\binom{8}{4}=\frac{70}{5}=14\).
\(C_3=\frac{1}{4}\binom{6}{3}=\frac{20}{4}=5\).

Example 11 — Parentheses

\(n=3\) balanced strings: ((())), (()()), (())(), ()(()), ()()(). Five \(=C_3\).

Example 12 — Binary trees

Plane binary trees with 3 internal nodes: \(C_3=5\) shapes.

Example 13 — Hockey-stick small

\(\binom{2}{2}+\binom{3}{2}+\binom{4}{2}+\binom{5}{2}=1+3+6+10=20=\binom{6}{3}\).

Example 14 — Identity challenge

Prove \(\sum_{k}\binom{n}{k}^2=\binom{2n}{n}\) via Vandermonde: \(\binom{n}{k}\binom{n}{n-k}\) and \(\binom{n+n}{n}\).

Example 15 — Expected weight lite

If each subset equally likely, expected size of random subset of \([n]\) is \(\frac{1}{2^n}\sum k\binom{n}{k}=\frac{n}{2}\).

Exercises

1. Expand \((x+2)^5\) fully.
   
2. Coefficient of \(x^2y^5\) in \((x+y)^7\); of \(x^4\) in \((1+x)^{12}\).
   
3. Prove Pascal combinatorially and algebraically (write both).
   
4. Prove \(k\binom{n}{k}=n\binom{n-1}{k-1}\) by double counting.
   
5. Evaluate \(\sum k\binom{n}{k}\) and \(\sum\binom{n}{k}\).
   
6. Prove alternating sum is \(0\) for \(n>0\) by pairing.
   
7. Vandermonde: verify for \(m=4,n=3,r=3\).
   
8. Hockey-stick: verify \(\sum_{i=3}^{7}\binom{i}{3}=\binom{8}{4}\).
   
9. Compute \(C_0\) through \(C_6\) by formula.
   
10. List all Dyck words for \(n=3\).
    
11. Show \(C_n=\binom{2n}{n}-\binom{2n}{n-1}\) equals \(\frac{1}{n+1}\binom{2n}{n}\).
    
12. Use recurrence to get \(C_4\) from smaller values.
    
13. Prove \(\sum\binom{n}{k}^2=\binom{2n}{n}\).
    
14. Coefficient of \(x^3\) in \((2+x)^6\).
    
15. Story for \(\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=2^n\).
    
16. How many subsets of \([10]\) have even size?
    
17. Expand \((x-y)^4\); check alternating pattern.
    
18. CS: number of ways \(2n\) calls push/pop on a stack stay valid—Catalan.
    
19. Multinomial: expand \((x+y+z)^2\).
    
20. Prove \(\binom{n}{k}/\binom{n}{k-1}=(n-k+1)/k\) for \(k\ge 1\).
    
21. Find \(n\) such that \(\binom{n}{2}=45\).
    
22. Row sum of Pascal row 8.
    
23. Challenge: reflection proof sketch for Catalan (optional paragraph).
    
24. Show \(\sum_{k\text{ even}}\binom{n}{k}=2^{n-1}\) for \(n\ge 1\).
    
25. Application: number of binary strings length \(2n\) with \(n\) zeros, \(n\) ones, all prefixes have #zeros ≥ #ones—Catalan.

CS connection

• Complexity / generating functions: \((1+x)^n\) tracks subset weights.
  
• Random algorithms: \(\sum k\binom{n}{k}/2^n=n/2\) average Hamming weight.
  
• Parsing / compilers: Catalan counts valid parenthesis and stack-sortable patterns.
  
• BST shapes: \(C_n\) binary search tree shapes on \(n\) keys (plane binary trees).
  
• Dynamic programming: binomial recurrences and Catalan recurrence are DP prototypes.

Common pitfalls

Pitfall	What to do instead
Mixing \(x^{n-k}y^k\) index conventions	Track which variable’s power is \(k\)
Forgetting \(n>0\) for alternating sum	\((1-1)^0=1\)
Catalan \(\binom{2n}{n}\) without \(1/(n+1)\)	Full central binomial is larger
Algebra only, no story	Both proofs strengthen memory
Off-by-one in Catalan index	\(C_n\) uses \(\binom{2n}{n}\), \(n\) pairs

Checkpoint

• State binomial theorem and prove via expansion story
  
• Pascal: combinatorial + algebraic
  
• Absorption and \(\sum k\binom{n}{k}=n2^{n-1}\)
  
• \(C_n=\frac{1}{n+1}\binom{2n}{n}\) and three interpretations
  
• Compute \(C_4\), \(C_5\) cold
  
• Exercises 1–15
  
• Vandermonde story in one sentence

Two personal takeaways:

1. …
   
2. …

Selected mini-solutions

2. \(\binom{7}{5}=21\); \(\binom{12}{4}=495\).
   
3. \(n2^{n-1}\); \(2^n\).
   
4. \(1,1,2,5,14,42,132\).
   
5. \(\binom{2n}{n}-\binom{2n}{n-1}=\binom{2n}{n}\bigl(1-\frac{n}{n+1}\bigr)=\frac{1}{n+1}\binom{2n}{n}\).
   
6. Vandermonde with \(m=n\), \(r=n\).
   
7. \(2^9=512\).
   
8. \(n(n-1)/2=45\Rightarrow n=10\).

Deepening notes

Algebraic induction template for binomial theorem

Base \(n=0\). Assume \((x+y)^{n-1}=\sum\binom{n-1}{k}x^{n-1-k}y^k\). Multiply by \((x+y)\); coefficient of \(x^{n-k}y^k\) is \(\binom{n-1}{k}+\binom{n-1}{k-1}\). Apply Pascal. Write this once without notes.

Generating identities from \((1+x)^n\)

Differentiate: \(n(1+x)^{n-1}=\sum k\binom{n}{k}x^{k-1}\); set \(x=1\) recover \(\sum k\binom{n}{k}=n2^{n-1}\).
Second derivative / \(x\) tricks give \(\sum k(k-1)\binom{n}{k}=n(n-1)2^{n-2}\).

Catalan reflection (outline)

Bad paths \((0,0)\to(n,n)\) that touch \(y=x+1\): reflect prefix until first touch over the line \(y=x+1\) to map bijectively to paths \((0,0)\to(n,n)\) with one extra North early—count \(\binom{2n}{n-1}\). Subtract from \(\binom{2n}{n}\).

Pascal triangle patterns

Row sums powers of 2; alternating row sums 0; hockey-stick along diagonals; binary carry patterns optional.

Extra drills

D1. Expand \((2x-y)^4\).
D2. Prove \(\sum (-1)^k\binom{n}{k}=0\) algebraically via \((1-1)^n\).
D3. Vandermonde numeric \(m=6,n=5,r=4\).
D4. Hockey-stick \(\sum_{i=2}^{8}\binom{i}{2}\).
D5. \(C_6\) by formula and by recurrence.
D6. List BST shapes for 3 keys.
D7. Coefficient of \(x^5\) in \((1+x+x^2/2!+\cdots)\) optional—skip; instead \((3+x)^5\) coeff of \(x^2\).
D8. Story for \(\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}\).

Flash

\((x+y)^n=\sum\binom{n}{k}x^{n-k}y^k\), \(C_n=\frac1{n+1}\binom{2n}{n}\), \(\sum k\binom{n}{k}=n2^{n-1}\).

Exam drill block

E1. Expand \((x+3)^4\) fully.
E2. Coeff of \(x^4y^3\) in \((x+y)^7\); of \(x^5\) in \((2+x)^8\).
E3. Prove Pascal combinatorially in ≤6 lines.
E4. Evaluate \(\sum k\binom{8}{k}\) and \(\sum\binom{8}{k}(-1)^k\).
E5. Vandermonde numeric: \(m=5,n=4,r=3\).
E6. Hockey-stick: \(\sum_{i=4}^{9}\binom{i}{4}\).
E7. Compute \(C_5\) two ways (formula + recurrence).
E8. List Dyck words for \(n=2\); count \(C_2\).
E9. Prove \(\sum\binom{n}{k}^2=\binom{2n}{n}\) via Vandermonde story.
E10. True/false: (i) \(C_n=\binom{2n}{n}\) (ii) \(\sum k\binom{n}{k}=n2^{n-1}\) (iii) alternating sum is \(0\) for \(n=0\).

Mini solutions

E1. \(x^4+12x^3+54x^2+108x+81\).
E2. \(\binom{7}{3}=35\); \(\binom{8}{5}2^{3}=56\cdot 8=448\).
E4. \(8\cdot 2^{7}=1024\); \(0\).
E5. \(\binom{9}{3}=84\).
E6. \(\binom{10}{5}=252\).
E7. \(C_5=42\).
E10. F; T; F (\((1-1)^0=1\)).

Synthesis

The binomial theorem equates algebra (expand products) with counting (choose \(k\) factors for \(y\)). Pascal, absorption, Vandermonde, and hockey-stick are the identity core—always keep a story and an algebra path. Catalan numbers package lattice-path, parentheses, and tree counts into one sequence; remember the \(1/(n+1)\) factor.

S1. Full dual proof of absorption.
S2. Catalan \(C_4\) by formula, recurrence, and parentheses list.
S3. Differentiate \((1+x)^n\) to recover \(\sum k\binom{n}{k}\) once without notes.

Tomorrow

Day 51 — Stars and bars: nonnegative and positive solutions to linear equations; multiset combinations; upper bounds via IE preview.