Combinatorics and Graph Theory · Problem 1.3.3

Fundamentals — David Guichard

Mathematics — Combinatorics · binomial-coefficients

Problem

Use a combinatorial argument to prove that

\displaystyle\sum_{k=0}^{n} \binom{k}{i} = \binom{n+1}{i+1}

for

n \geq 0

and

i \geq 0

; that is, explain why the left-hand side counts the same thing as the right-hand side.