# Pascal's Rule/Direct Proof

## 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

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

 $\displaystyle \binom n k + \binom n {k - 1}$ $=$ $\displaystyle \frac {n!} {k! \, \paren {n - k}!} + \frac {n!} {\paren {k - 1}! \, \paren {n - \paren {k - 1} }!}$ Definition of Binomial Coefficient $\displaystyle$ $=$ $\displaystyle \frac {n! \, \paren {n - \paren {k - 1} } } {k! \, \paren {n - k}! \, \paren {n - \paren {k - 1} } } + \frac {n! \, k} {\paren {k - 1}! \, \paren {n - \paren {k - 1} }! \ k}$ $\displaystyle$ $=$ $\displaystyle \frac {n! \, \paren {n - k + 1} } {k! \, \paren {n - k + 1}!} + \frac {n! \, k} {k! \, \paren {n - k + 1}!}$ $\displaystyle$ $=$ $\displaystyle \frac {n! \, \paren {n - k + 1} + n! \, k} {k! \, \paren {n - k + 1}!}$ $\displaystyle$ $=$ $\displaystyle \frac {n! \, \paren {n - k + 1 + k} } {k! \, \paren {n - k + 1}!}$ $\displaystyle$ $=$ $\displaystyle \frac {n! \, \paren {n + 1} } {k! \, \paren {n - k + 1}!}$ $\displaystyle$ $=$ $\displaystyle \frac {\paren {n + 1}!} {k! \, \paren {n + 1 - k}!}$ $\displaystyle$ $=$ $\displaystyle \binom {n + 1} k$ Definition of Binomial Coefficient

$\blacksquare$

## Source of Name

This entry was named for Blaise Pascal.