Pascal's Rule

Theorem

Let $\displaystyle \binom n k$ be a binomial coefficient.

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

$\displaystyle \binom n {k-1} + \binom n k = \binom {n+1} k$

This is also valid for the real number definition:

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

Direct Proof

Let $n, k \in \N$ with $1 \le k \le n$.

	\(\displaystyle \)	\(\displaystyle \binom n k + \binom n {k-1}\)	\(=\)	\(\displaystyle \frac{n!}{k! (n-k)!} + \frac{n!}{(k-1)!(n-(k-1))!}\)	\(\displaystyle \)	Definition of Binomial Coefficient
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac{n!(n-(k-1))}{k!(n-k)!(n-(k-1))} + \frac{n!k}{(k-1)!(n-(k-1))!k}\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac{n!(n-k+1)}{k!(n-k+1)!} + \frac{n!k}{k!(n-k+1)!}\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac{n!(n-k+1) + n!k}{k!(n-k+1)!}\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac{n!(n-k+1+k)}{k!(n-k+1)!}\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac{n!(n+1)}{k!(n-k+1)!}\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac{(n+1)!}{k!(n+1-k)!}\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \binom {n+1} k\)	\(\displaystyle \)

$\blacksquare$

Combinatorial 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 $\displaystyle \binom {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 $\displaystyle \binom 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 $\displaystyle \binom n {k-1}$ ways of selecting the other $k-1$ members so as to form such a committee.

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

Hence the result.

$\blacksquare$

Proof for Real Numbers

Follows directly from Factors of Binomial Coefficients:

	\(\displaystyle \)	\(\displaystyle \)	\(\)	\(\displaystyle \left({r + 1}\right) \binom r {k - 1} + \left({r + 1}\right) \binom r k\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle k \binom {r + 1} k + \left({r + 1 - k}\right) \binom {r + 1} k\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({r + 1}\right) \binom {r + 1} k\)	\(\displaystyle \)

Dividing by $\left({r + 1}\right)$ yields the solution.

$\blacksquare$

Also see

• Pascal's Triangle

Source of Name

This entry was named for Blaise Pascal.

Sources

• Seth Warner: Modern Algebra (1965): $\S 19$: Theorem $19.10$
• Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (1968): $\S 1.2.6 \ \text{D}$
• Murray R. Spiegel: Mathematical Handbook of Formulas and Tables (1968): $3.6$
• George E. Andrews: Number Theory (1971): $\S 3.1$: Exercise $3$
• K.G. Binmore: Mathematical Analysis: A Straightforward Approach (1977)... (previous)... (next): $\S 3.11 \ (4)$