Pascal's Rule/Direct 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

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.


Sources