Understanding Pascal's Identity
Pascal's Identity is one of the most important relationships in combinatorics. It states that the number of ways to choose $r$ items from $n+1$ total items is the sum of the ways to choose $r$ items from $n$ items, plus the ways to choose $r-1$ items from $n$ items.
Mathematically, it is expressed as: $$C(n, r) + C(n, r-1) = C(n+1, r)$$
Algebraic Proof
To prove this, we use the definition of combinations: $C(n, r) = \frac{n!}{r!(n-r)!}$.
Expand the left side: $$C(n, r) + C(n, r-1) = \frac{n!}{r!(n-r)!} + \frac{n!}{(r-1)!(n-r+1)!}$$
Find a common denominator: The common denominator is $r!(n-r+1)!$. Multiply the first term by $\frac{n-r+1}{n-r+1}$ and the second by $\frac{r}{r}$: $$= \frac{n!(n-r+1) + n!(r)}{r!(n-r+1)!}$$
Simplify the numerator: Factor out $n!$: $$= \frac{n!(n-r+1 + r)}{r!(n-r+1)!} = \frac{n!(n+1)}{r!(n-r+1)!}$$
Final Result: Since $n!(n+1) = (n+1)!$ and $(n-r+1)! = ((n+1)-r)!$, we get: $$= \frac{(n+1)!}{r!((n+1)-r)!} = C(n+1, r)$$
Combinatorial Intuition
Imagine you have a set of $n+1$ balls, one of which is special (let's call it 'Ball X'). You want to choose $r$ balls in total.
- Case 1: You do not pick Ball X. You must choose all $r$ balls from the remaining $n$ balls. There are $C(n, r)$ ways to do this.
- Case 2: You do pick Ball X. You still need $r-1$ more balls to complete your set of $r$, which must be chosen from the remaining $n$ balls. There are $C(n, r-1)$ ways to do this.
Summing these two disjoint cases gives you the total ways to choose $r$ items from $n+1$ items.