Dixon's Identity/General Case
Jump to navigation
Jump to search
Theorem
For $l, m, n \in \Z_{\ge 0}$:
- $\ds \sum_{k \mathop \in \Z} \paren {-1}^k \dbinom {l + m} {l + k} \dbinom {m + n} {m + k} \dbinom {n + l} {n + k} = \dfrac {\paren {l + m + n}!} {l! \, m! \, n!}$
Proof
- $\ds \sum_{k \mathop \in \Z} \binom {m - r + s} k \binom {n + r - s} {n - k} \binom {r + k} {m + n} = \binom r m \binom s n$
Setting $\tuple {m, n, r, s, k} \gets \tuple {m + k, l - k, m + n, n + l, j}$ into the equation above, we obtain:
\(\ds \binom r m \binom s n\) | \(=\) | \(\ds \sum_{j \mathop \in \Z} \binom {m - r + s} k \binom {n + r - s} {n - k} \binom {r + k} {m + n}\) | before substitution | |||||||||||
\(\ds \binom {m + n} {m + k} \binom {n + l} {l - k}\) | \(=\) | \(\ds \sum_{j \mathop \in \Z} \binom {\paren {m + k} - \paren {m + n} + \paren {n + l} } j \binom {\paren {l - k} + \paren {m + n} - \paren {n + l} } {\paren {l - k} - j} \binom {\paren {m + n } + j} {\paren {m + k} + \paren {l - k} }\) | after substitution | |||||||||||
\(\ds \binom {m + n} {m + k} \binom {n + l} {n + k}\) | \(=\) | \(\ds \sum_{j \mathop \in \Z} \binom {l + k} j \binom {m - k} {l - k - j} \binom {m + n + j} {m + l}\) | simplifying and Symmetry Rule for Binomial Coefficients |
On the left hand side, we have:
\(\ds \sum_{k \mathop \in \Z} \paren {-1}^k \dbinom {l + m} {l + k} \dbinom {m + n} {m + k} \dbinom {n + l} {n + k}\) | \(=\) | \(\ds \sum_{k \mathop \in \Z} \paren {-1}^k \dbinom {l + m} {l + k} \paren {\sum_{j \mathop \in \Z} \binom {l + k} j \binom {m - k} {l - k - j} \binom {m + n + j} {m + l} }\) | substituting from above | |||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{k \mathop \in \Z} \sum_{j \mathop \in \Z} \paren {-1}^k \dbinom {l + m} {l + k} \dbinom {l + k} j \dbinom {m - k} {l - k - j} \dbinom {m + n + j} {m + l}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{k \mathop \in \Z} \sum_{j \mathop \in \Z} \paren {-1}^k \dfrac {\paren {l + m}!} {\paren {l + k}!\paren {m - k}!} \dfrac {\paren {l + k}!} {j!\paren {l - j + k}!} \dfrac {\paren {m - k}!} {\paren {l - j - k}!\paren {j - l + m}!} \dfrac {\paren {m + n + j}!} {\paren {m + l}!\paren {j - l + n}!}\) | Definition of Binomial Coefficient | |||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{k \mathop \in \Z} \sum_{j \mathop \in \Z} \paren {-1}^k \dfrac 1 {j!\paren {l - j + k}!} \dfrac 1 {\paren {l - j - k}!\paren {j - l + m}!} \dfrac {\paren {m + n + j}!} {\paren {j - l + n}!}\) | $\paren {l + m}!$, $\paren {l + k}!$ and $\paren {m - k}!$ cancel |
Unless $j = l$ and $k = 0$ the sum on $k$ vanishes.
Therefore:
- $\ds \sum_{k \mathop \in \Z} \paren {-1}^k \dbinom {l + m} {l + k} \dbinom {m + n} {m + k} \dbinom {n + l} {n + k} = \dfrac {\paren {l + m + n}!} {l! \, m! \, n!}$
$\blacksquare$
Source of Name
This entry was named for Alfred Cardew Dixon.
Sources
- 1903: A.C. Dixon: Summation of a certain Series (Proc. London Math. Soc. Vol. 35: pp. 285 – 289)
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.6$: Binomial Coefficients: Exercise $62$