Pascal's Rule/Combinatorial Proof

From ProofWiki
Jump to navigation Jump to search

Theorem

For positive integers $n, k$ with $1 \le k \le n$:

$\dbinom n {k - 1} + \dbinom n k = \dbinom {n + 1} k$

This is also valid for the real number definition:

$\forall r \in \R, k \in \Z: \dbinom r {k - 1} + \dbinom r k = \dbinom {r + 1} k$


Proof

Suppose you were a member of a club with $n + 1$ members (including you).

Suppose it were time to elect a committee of $k$ members from that club.

From Cardinality of Set of Subsets, there are $\dbinom {n + 1} k$ ways to select the members to form this committee.


Now, you yourself may or may not be elected a member of this committee.


Suppose that, after the election, you are not a member of this committee.

Then, from Cardinality of Set of Subsets, there are $\dbinom n k$ ways to select the members to form such a committee.


Now suppose you are a member of the committee. Apart from you, there are $k - 1$ such members.

Again, from Cardinality of Set of Subsets, there are $\dbinom n {k - 1}$ ways of selecting the other $k - 1$ members so as to form such a committee.


In total, then, there are $\dbinom n k + \dbinom n {k - 1}$ possible committees.

Hence the result.

$\blacksquare$


Source of Name

This entry was named for Blaise Pascal.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Pascal%27s_Rule/Combinatorial_Proof&oldid=596395"