Pascal's rule

In mathematics, Pascal's rule is a combinatorial identity about binomial coefficients. It states that for any natural number n we have

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

where $1\leq k<n$ and ${n \choose k}$ is a binomial coefficient.

Combinatorial proof

Pascal's rule has an intuitive combinatorial meaning. Recall that ${a \choose b}$ counts in how many ways can we pick a subset with b elements out from a set with a elements. Therefore, the right side of the identity ${n \choose k}$ is counting how many ways can we get a k-subset out from a set with n elements.

Now, suppose you distinguish a particular element 'X' from the set with n elements. Thus, every time you choose k elements to form a subset there are two possibilities: X belongs to the chosen subset or not.

If X is in the subset, you only really need to choose k-1 more objects (since it is known that X will be in the subset) out from the remaining n-1 objects. This can be accomplished in $n-1 \choose k-1$ ways.

When X is not in the subset, you need to choose all the k elements in the subset from the n-1 objects that are not X. This can be done in $n-1 \choose k$.

We conclude that the numbers of ways to get a k-subset from the n-set, which we know is ${n \choose k}$, is also the number ${n-1 \choose k-1}+{n-1 \choose k}$.

Algebraic proof

We need to show

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

Let us begin by writing the left-hand side as

${\frac {n!}{k!(n-k)!}}+{\frac {n!}{(k-1)!(n-(k-1))!}}$

Getting a common denominator and simplifying, we have

${\frac {n!}{k!(n-k)!}}+{\frac {n!}{(k-1)!(n-k+1)!}}$

$=$ ${\frac {(n-k+1)n!}{(n-k+1)k!(n-k)!}}+{\frac {kn!}{k(k-1)!(n-k+1)!}}$

$=$ ${\frac {(n-k+1)n!+kn!}{k!(n-k+1)!}}$

$=$ ${\frac {(n+1)n!}{k!((n+1)-k)!}}$

$=$ ${\frac {(n+1)!}{k!((n+1)-k)!}}$

$=$ ${n+1 \choose k}$

See also

• Pascal's Triangle

Sources

• Pascal's rule at PlanetMath.
• Pascal's rule proof at PlanetMath.

External links

• "Central binomial coefficient". PlanetMath.
• "Binomial coefficient". PlanetMath.
• "Pascal's triangle". PlanetMath.