Chu-Vandermonde Identity/Falling Factorial Variant

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $r, s \in \R, n \in \Z_{\ge 0}$.

Then:

$\ds \sum_{k \mathop = 0}^n \dbinom n k r^{\underline k} s^{\underline {n-k} } = \paren {r + s}^{\underline n}$


Proof

\(\ds \sum_{k \mathop = 0}^n \dbinom n k r^{\underline k} s^{\underline {n-k} }\) \(=\) \(\ds \sum_{k \mathop = 0}^n \paren {\dfrac {n!} {k! \paren{n - k}!} } \paren{ \dfrac {r!} {\paren {r - k}!} } \paren{ \dfrac {s!} {\paren {s - \paren {n - k} }!} }\) Definition of Binomial Coefficient and Definition of Falling Factorial
\(\ds \) \(=\) \(\ds n! \sum_{k \mathop = 0}^n {\dbinom r k} \dbinom s {n - k}\) Definition of Binomial Coefficient
\(\ds \) \(=\) \(\ds n! \binom {r + s } n\) Chu-Vandermonde Identity
\(\ds \) \(=\) \(\ds n! \dfrac {\paren {r + s}!} {n! \paren {r + s - n}!}\) Definition of Binomial Coefficient
\(\ds \) \(=\) \(\ds \paren{r + s}^{\underline n}\) Definition of Falling Factorial

$\blacksquare$


Also known as

This identity is also known as Vandermonde's formula.


Source of Name

This entry was named for Chu Shih-Chieh and Alexandre-Théophile Vandermonde.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Chu-Vandermonde_Identity/Falling_Factorial_Variant&oldid=608095"