Concrete Math Chap 5 - Binomial Coefficients

Posted on Edited on Word count in article: 1.8k Reading time ≈ 3 mins.

111

Formulas and Tricks

\[ \begin{align} \binom{n}{k} &= \frac{n!}{k!(n-k)!}, \quad \text{integers } n \ge k \ge 0. \quad \text{factorial expansion} \\ \binom{n}{k} &= \binom{n}{n-k}, \quad \text{integer } n \ge 0, \text{ integer } k. \quad \text{symmetry} \\ \binom{r}{k} &= \frac{r}{k}\binom{r-1}{k-1}, \quad \text{integer } k \ne 0. \quad \text{absorption/extraction} \\ \binom{r}{k} &= \binom{r-1}{k} + \binom{r-1}{k-1}, \quad \text{integer } k. \quad \text{addition/induction} \\ \binom{r}{k} &= (-1)^k \binom{k-r-1}{k}, \quad \text{integer } k. \quad \text{upper negation} \\ \binom{r}{m}\binom{m}{k} &= \binom{r}{k}\binom{r-k}{m-k}, \quad \text{integers } m, k. \quad \text{trinomial revision} \\ \sum_k \binom{r}{k} x^k y^{r-k} &= (x+y)^r, \quad \text{integer } r \ge 0, \text{ or } |x/y| < 1. \quad \text{binomial theorem} \\ \sum_{k \le n} \binom{r+k}{k} &= \binom{r+n+1}{n}, \quad \text{integer } n. \quad \text{parallel summation} \\ \sum_{0 \le k \le n} \binom{k}{m} &= \binom{n+1}{m+1}, \quad \text{integers } m, n \ge 0. \quad \text{upper summation} \\ \sum_k \binom{r}{k} \binom{s}{n-k} &= \binom{r+s}{n}, \quad \text{integer } n. \quad \text{Vandermonde convolution} \end{align} \]

Exercise

  1. Express the function \(G(z)\) in the formula \[ F \left( \begin{matrix} a_1, \dots, a_m \\ b_1, \dots, b_n \end{matrix} \middle| z \right) = 1 + G(z) \] as a multiple of a hypergeometric series.

    This is a summary

    Solution

    asdsa

  2. Prove that \[ F \left( \begin{matrix} a_1, a_1 + \frac{1}{2}, \dots, a_m, a_m + \frac{1}{2} \\ b_1, b_1 + \frac{1}{2}, \dots, b_n, b_n + \frac{1}{2} \end{matrix} \middle| (2^{m-n-1}z)^2 \right) = \frac{1}{2} \left( F \left( \begin{matrix} 2a_1, \dots, 2a_m \\ 2b_1, \dots, 2b_n \end{matrix} \middle| z \right) + F \left( \begin{matrix} 2a_1, \dots, 2a_m \\ 2b_1, \dots, 2b_n \end{matrix} \middle| -z \right) \right). \]

  3. Prove Euler's identity \[ F \left( \begin{matrix} a, b \\ c \end{matrix} \middle| z \right) = (1-z)^{c-a-b} F \left( \begin{matrix} c-a, c-b \\ c \end{matrix} \middle| z \right) \] by applying Pfaff's reflection law (5.101) twice.