Guichard-Combinatorics-Graph-Theory · Problem 1.3.3

Fundamentals

Mathematics — Probability · binomial-coefficients

Problem

Use a combinatorial argument to prove that

\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.