Day 56 — Story proofs

Day 56 — Story proofs

Stage V · concept day
Goal: Prove binomial identities by combinatorial stories (double counting and bijections); contrast with algebraic proofs; master Pascal, absorption, Vandermonde, and hockey-stick.

Why this matters

A story proof explains why an identity is true by counting the same set two ways (or exhibiting a bijection). In CS interviews and paper proofs, a one-paragraph combinatorial argument often beats page-long algebra. Algebra still matters for verification; stories give insight and prevent cargo-cult formula use.

Theory

Combinatorial vs algebraic proofs

Style	What you do	Strength
Algebraic	Manipulate factorials, induct, use generating functions	Mechanical, rigorous once steps OK
Combinatorial / story	Interpret both sides as counting the same family of objects	Explains meaning; often shorter
Bijective	Explicit invertible map between two sets	Strongest “same size” certificate

Good practice: do both for core identities.

Double counting

To prove \(LHS=RHS\):

1. Describe a set \(S\) of configurations.
   
2. Show \(|S|=LHS\) by one classification.
   
3. Show \(|S|=RHS\) by another.
   
4. Conclude equality.

Bijective proofs

Exhibit \(f:A\to B\) invertible (or describe inverse). Then \(|A|=|B|\).
Example: \(k\)-subsets ↔︎ complements ↔︎ \((n-k)\)-subsets gives \(\binom{n}{k}=\binom{n}{n-k}\).

Pascal’s identity (both proofs)

\[ \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}. \]

Story: \(k\)-subsets of \([n]\); distinguish whether \(n\in S\) or not.
Algebra: Day 50.

Absorption / committee chair

\[ k\binom{n}{k}=n\binom{n-1}{k-1}. \]

Story: committees of \(k\) with a chair from the committee—two counting orders.

Symmetry

\[ \binom{n}{k}=\binom{n}{n-k}. \]

Bijection: \(S\mapsto [n]\setminus S\).

Sum of binomials

\[ \sum_{k=0}^{n}\binom{n}{k}=2^n. \]

Story: LHS subsets by size; RHS each element in/out.

Alternating sum / parity

\[ \sum_{k}(-1)^k\binom{n}{k}=0\quad(n>0). \]

Story: even-sized and odd-sized subsets equally many via \(S\leftrightarrow S\triangle\{x\}\).

Vandermonde

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

Story: \(r\)-subsets from \(m\) men + \(n\) women, classified by number of men.

Hockey-stick identity

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

Story: Count \((r+1)\)-subsets of \([n+1]=\{1,2,\ldots,n+1\}\).
Let \(S\) be such a subset; let \(m=\max S\). Then \(m\) ranges from \(r+1\) to \(n+1\), and the remaining \(r\) elements are chosen from \(\{1,\ldots,m-1\}\): \(\binom{m-1}{r}\) ways.
Sum \(\sum_{m=r+1}^{n+1}\binom{m-1}{r}=\sum_{i=r}^{n}\binom{i}{r}\) with \(i=m-1\).
RHS: \(\binom{n+1}{r+1}\). \(\square\)

Algebraic path: Pascal telescope \(\binom{i+1}{r+1}-\binom{i}{r+1}=\binom{i}{r}\), sum both sides.

Parallel sum identity

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

Story: pick distinguished element in subset: choose element (\(n\)) then any subset of rest (\(2^{n-1}\)).

Block-walking / lattice path stories

\(\binom{a+b}{a}\) paths; Pascal: last step East or North.
Vandermonde: path through a diagonal cut.

When stories fail (honestly)

Some identities (e.g. sophisticated \(q\)-analogs, highly alternating multi-sums) resist simple stories. Algebra and GF remain essential. Prefer stories when both sides clearly count.

Proof hygiene

• Name the set of objects in the first sentence.
  
• “LHS counts by …” / “RHS counts by …”
  
• Avoid double-counting within one side unless intentional and corrected.
  
• Check small \(n\) numerically first.

Worked examples

Example 1 — Symmetry bijection

Write \(f(S)=[n]\setminus S\); \(f\circ f=\mathrm{id}\); maps \(k\)-sets to \((n-k)\)-sets.

Example 2 — Pascal numeric

\(n=6,k=2\): \(15=10+5\).

Example 3 — Chair

\(n=10,k=3\): \(3\binom{10}{3}=360=10\binom{9}{2}\).

Example 4 — Vandermonde numeric

\(m=n=3,r=3\): \(\binom{6}{3}=20=\sum_k\binom{3}{k}\binom{3}{3-k}\).

Example 5 — Hockey-stick numeric

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

Example 6 — Algebraic hockey-stick telescope

\(\binom{i}{r}=\binom{i+1}{r+1}-\binom{i}{r+1}\); sum \(i=r\) to \(n\) telescopes to \(\binom{n+1}{r+1}-\binom{r}{r+1}=\binom{n+1}{r+1}\).

Example 7 — \(\sum\binom{n}{k}^2=\binom{2n}{n}\)

Choose \(n\) people from \(n\) men + \(n\) women: Vandermonde with \(k\) men gives \(\sum\binom{n}{k}\binom{n}{n-k}=\sum\binom{n}{k}^2\).

Example 8 — Bit-string story

Number of length-\(n\) strings with odd parity equals even: \(2^{n-1}\) each—pair flip first bit.

Example 9 — Paths Pascal

Paths to \((n-k,k)\): last step from \((n-k-1,k)\) or \((n-k,k-1)\).

Example 10 — Committee with roles

Number of ways to choose president and \(k-1\) other members: \(n\binom{n-1}{k-1}=\binom{n}{k}k\).

Example 11 — Non-story failure mode

“Both sides equal 6” for specific \(n\) is not a proof of identity for all \(n\).

Example 12 — Injection story for inequality

\(\binom{n}{k}\le 2^n\) because \(k\)-sets inject into all subsets.

Example 13 — Double count edges of \(K_n\)

\(\binom{n}{2}\) vs \(\frac{1}{2}\sum_v\deg(v)\) handshaking—graph Day 59, same method.

Example 14 — Choose then order

\(P(n,k)=\binom{n}{k}k!\): LHS ordered tuples; RHS choose set then permute.

Example 15 — Write a full formal story proof

Theorem. \(\sum_{k=0}^{n}k\binom{n}{k}=n2^{n-1}\).
Proof. Let \(S\) be the set of pairs \((A,x)\) with \(A\subseteq[n]\), \(x\in A\).
Count \(|S|\): for each \(k\), \(\binom{n}{k}\) choices of \(A\) with \(|A|=k\) and \(k\) choices of \(x\): \(\sum k\binom{n}{k}\).
Alternatively: choose \(x\in[n]\) first (\(n\) ways), then \(A\setminus\{x\}\) any subset of \([n]\setminus\{x\}\) (\(2^{n-1}\) ways).
Thus equality. \(\square\)

Exercises

1. Prove \(\binom{n}{k}=\binom{n}{n-k}\) bijectively.
   
2. Prove Pascal combinatorially.
   
3. Prove absorption combinatorially.
   
4. Prove \(\sum\binom{n}{k}=2^n\) two ways (story + induction).
   
5. Prove alternating sum by pairing for \(n>0\).
   
6. Prove Vandermonde by story.
   
7. Prove hockey-stick by max-element story.
   
8. Prove hockey-stick by Pascal telescope.
   
9. Prove \(\sum k\binom{n}{k}=n2^{n-1}\) formally as in Ex. 15.
   
10. Prove \(\sum\binom{n}{k}^2=\binom{2n}{n}\).
    
11. Give a lattice-path proof of Pascal.
    
12. Prove \(P(n,k)=\binom{n}{k}k!\) by story.
    
13. Combinatorial proof: \(\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots=\sum_{k\text{ even?}}\) wait—prove even = odd = \(2^{n-1}\).
    
14. Story for \(\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}\) (reindex Pascal).
    
15. Why is “count the same thing two ways” valid logic? (One paragraph on equinumerosity.)
    
16. Algebraic proof of absorption from factorials.
    
17. Challenge: combinatorial proof of \(\sum_{k}k(k-1)\binom{n}{k}=n(n-1)2^{n-2}\).
    
18. Find a story for \(\binom{2n}{n}/(n+1)\) being integer (Catalan)—interpretations Day 50.
    
19. Double-count: number of functions \([k]\to[n]\) vs something? (\(n^k\))—optional.
    
20. Write the worst fake story proof for Pascal and mark the flaw.
    
21. Hockey-stick application: simplify \(\binom{5}{2}+\binom{6}{2}+\cdots+\binom{20}{2}\).
    
22. Prove \(\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}\) by committee story.
    
23. CS: story for number of \(n\)-bit strings = number of subsets of flags.
    
24. Compare length of algebraic vs story proof for Ex. 22.
    
25. Portfolio: pick 3 identities and write exam-quality story proofs.

CS connection

• Algorithm correctness: counting arguments (amortized, potential) often double-count operations.
  
• Hashing analysis: balls-and-bins stories.
  
• Coding theory: weight enumerators and identities.
  
• Interview signal: story proofs show conceptual mastery beyond memorization.
  
• Compiler / SSA / graph: handshaking-style double counts reappear in Stage VI.

Common pitfalls

Pitfall	What to do instead
Story that only works for special \(n\)	Keep \(n\) general
Hidden overcount on one side	Check with small numbers
“Clearly the same” without map	Define the bijection
Algebra errors after story	Still verify small \(n\)
Confusing \(\sum_i\binom{i}{r}\) limits	Hockey-stick bounds careful

Checkpoint

• Double counting template cold
  
• Pascal + absorption + Vandermonde stories
  
• Hockey-stick full proof
  
• \(\sum k\binom{n}{k}\) formal writeup
  
• One bijective proof
  
• Exercises 1–15
  
• Three identities in personal portfolio

Two personal takeaways:

1. …
   
2. …

Selected mini-solutions

13. Pairing with fixed \(x\).
    
14. Choose 2 distinguished ordered members in subset: \(n(n-1)2^{n-2}\).
    
15. \(\sum_{i=5}^{20}\binom{i}{2}=\binom{21}{3}-\binom{5}{3}=1330-10=1320\).
    
16. Choose \(k\) leaders then \(m-k\) ordinary from rest; or choose \(m\) then \(k\) leaders among them.

Deepening notes

Story proof rubric (self-grade)

Criterion	Pass?
Object set \(S\) named in sentence 1
LHS interpretation clear
RHS interpretation clear
No hidden overcount
Checked small \(n\)

Bijection checklist

Define \(f:A\to B\), define \(g:B\to A\), check \(g\circ f=\mathrm{id}_A\) and \(f\circ g=\mathrm{id}_B\)—or argue obvious invertibility carefully.

Hockey-stick memory hook

“Sum a diagonal of Pascal’s triangle to get the next entry off the diagonal.”
\(\sum_{i=r}^{n}\binom{i}{r}=\binom{n+1}{r+1}\).

Extra formal writeups to practice

1. Symmetry bijection (full).
   
2. Pascal distinguished element (full).
   
3. Absorption chair (full).
   
4. \(\sum k\binom{n}{k}\) pairs (full).
   
5. Vandermonde men/women (full).
   
6. Hockey-stick max element (full).
   
7. \(\sum\binom{n}{k}^2=\binom{2n}{n}\) (full).
   
8. \(P(n,k)=\binom{n}{k}k!\) (full).

Anti-patterns

• “Both sides count ways to choose, QED” without specifying from what.
  
• Using a story that assumes \(k\) fixed incorrectly.
  
• Algebraic cancellation disguised as a story.

Exam drill block

E1. Story-prove \(\binom{n}{k}=\binom{n}{n-k}\).
E2. Story-prove Pascal.
E3. Story-prove absorption \(k\binom{n}{k}=n\binom{n-1}{k-1}\).
E4. Double-count \(\sum k\binom{n}{k}=n2^{n-1}\).
E5. Vandermonde men/women story for \(\binom{m+n}{r}\).
E6. Hockey-stick: full max-element writeup \(\sum_{i=r}^{n}\binom{i}{r}=\binom{n+1}{r+1}\).
E7. Bijective: even vs odd sized subsets for \(n\ge 1\).
E8. Story for \(P(n,k)=\binom{n}{k}k!\).
E9. True/false: (i) story proofs need \(n\) specific (ii) both sides must count the same set \(S\) (iii) small-\(n\) check is optional fluff.
E10. Write \(\sum\binom{n}{k}^2=\binom{2n}{n}\) as choosing \(n\) from \(n\) red + \(n\) blue.

Mini solutions

E1. Complement map \(A\mapsto S\setminus A\) is a bijection \(k\)-sets ↔︎ \((n-k)\)-sets.
E4. Pick distinguished member first (\(n\)), free subset of rest (\(2^{n-1}\)).
E7. Fix \(x\); toggle membership of \(x\) pairs even/odd.
E9. F; T; F (mandatory sanity).
E10. Vandermonde with \(m=n\), choose \(k\) red and \(n-k\) blue, sum on \(k\).

Portfolio identities (write full proofs offline)

1. Symmetry
   
2. Pascal
   
3. Absorption
   
4. \(\sum\binom{n}{k}=2^n\)
   
5. \(\sum k\binom{n}{k}=n2^{n-1}\)
   
6. Vandermonde
   
7. Hockey-stick
   
8. \(\sum\binom{n}{k}^2=\binom{2n}{n}\)

Synthesis

Story proofs double-count or biject. Name the set \(S\) of objects first; interpret LHS and RHS as two counting procedures on \(S\). Check a small \(n\). Algebra still matters for confidence, but the story is what transfers to new identities.

S1. Full formal hockey-stick from memory.
S2. One original identity with a story (even a simple product).
S3. Cold: absorption + Pascal stories in under two minutes each.

Tomorrow

Day 57 — Counting workshop: mixed hard set spanning product through IE and recurrences; method selection guide.