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$.

\(\ds \binom n k + \binom n {k - 1}\) \(=\) \(\ds \frac {n!} {k! \, \paren {n - k}!} + \frac {n!} {\paren {k - 1}! \, \paren {n - \paren {k - 1} }!}\) Definition of Binomial Coefficient
\(\ds \) \(=\) \(\ds \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}\) multiplying by $1$
\(\ds \) \(=\) \(\ds \frac {n! \, \paren {n - k + 1} } {k! \, \paren {n - k + 1}!} + \frac {n! \, k} {k! \, \paren {n - k + 1}!}\) Definition of Factorial
\(\ds \) \(=\) \(\ds \frac {n! \, \paren {n - k + 1} + n! \, k} {k! \, \paren {n - k + 1}!}\) Addition of Fractions
\(\ds \) \(=\) \(\ds \frac {n! \, \paren {n - k + 1 + k} } {k! \, \paren {n - k + 1}!}\)
\(\ds \) \(=\) \(\ds \frac {n! \, \paren {n + 1} } {k! \, \paren {n - k + 1}!}\)
\(\ds \) \(=\) \(\ds \frac {\paren {n + 1}!} {k! \, \paren {n + 1 - k}!}\) Definition of Factorial
\(\ds \) \(=\) \(\ds \binom {n + 1} k\) Definition of Binomial Coefficient

$\blacksquare$


Source of Name

This entry was named for Blaise Pascal.


Sources

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