Proof of Tartaglia's formula

The recursive formula $\dbinom{n}{k} = \dbinom{n-1}{k-1} + \dbinom{n-1}{k}$ is proved by a simple combinatorial argument, distinguishing two cases.

Proof — Tartaglia's formula

Consider a set of $n$ objects, one of which is “special”. A subset of $k$ elements either contains the special one or it does not:

• if it contains it, the remaining $k-1$ are chosen from the other $n-1$: $\dbinom{n-1}{k-1}$ ways;
• if it does not contain it, all $k$ are chosen from the other $n-1$: $\dbinom{n-1}{k}$ ways.

The sum covers all subsets of $k$ elements, that is $\dbinom{n}{k}$. $\blacksquare$

Links

Topics: Combinatorics
Concepts: Binomial coefficient · Tartaglia’s triangle
Methods: Tartaglia triangle
Skills: Proving · Reasoning by cases
People: Niccolò Tartaglia