Enumerative Combinatorics · Binomial and multinomial coefficients, identities, and lattice paths

Let a,b ≥ 0 and let k be an integer

Problem

Let $a,b\ge 0$ and let $k$ be an integer. Prove Vandermonde's identity \[ \sum_{j\in\mathbb Z}\binom aj\binom b{k-j}=\binom{a+b}{k}, \] where only finitely many terms are nonzero. Give both a subset proof and a proof by comparing coefficients in $(1+x)^a(1+x)^b$. Eight distinct silver badges and five distinct copper badges are available. Count the four-badge selections by their number of silver badges and verify the resulting total. Explain why the possible values of $j$ are automatically enforced by the zero convention.

Hint

Split a $k$-element selection by how many objects came from the first class.

Check your work

Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.

Check your answer See the full solution

The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Enumerative Combinatorics sample problem: Try the free sample problem.

More Enumerative Combinatorics practice problems

A group has six distinct volunteersCounting principles, bijections, and the pigeonhole principle
Among n distinct volunteers, a specified set of r volunteers is qualified to serve as…Counting principles, bijections, and the pigeonhole principle
Let a,b ≥ 0 and h ≥ 1 be integers with b-a<hBinomial and multinomial coefficients, identities, and lattice paths
For n ≥ 1, a positive composition of n is an ordered list of positive integers summing…Compositions, multisets, and distributing objects into boxes
Among thirty labeled projects, eighteen use method A, fourteen use method B, and twelve…Inclusion-exclusion, derangements, and surjections
Let S(n,k) count partitions of [n] into k nonempty unordered blocksSet partitions, Stirling numbers, and the cycle structure of permutations
An integer partition of n is a finite weakly decreasing sequence of positive integers…Integer partitions and Ferrers diagrams
Let a₀=2, a₁=5, and aₙ=5aₙ₋₁-6aₙ₋₂ for n ≥ 2Ordinary generating functions, recurrences, and Catalan numbers
If aₙ counts structures on a specified set of n distinct labels, its exponential…Exponential generating functions and labeled structures