Exercises from Section 1.2.6

There are $(\binom{n}{n - 1}) = n$ combinations of $n$ things taken $n - 1$ at a time. Intuitively, each distinct set of $n - 1$ objects leaves out a single item, and there are $n$ items.

We have

\begin{array}{l} (\binom{0}{0}) & = \frac{0!}{0! (0 - 0)!} \\ = \frac{1}{1} \\ = 1 . \end{array}

Intuitively, there is only a single way to choose nothing from nothing.

There are $(\binom{52}{13}) = 635013559600$ possible bridge hands, as we are choosing 13 from 52 things.

The answer to exercise 3 was $(\binom{52}{13}) = \frac{52!}{13! (52 - 13)!} = \frac{52!}{13! 39!}$ . We can use Eq. 1.2.5-(8) to determine the prime factorization of each factorial and then the answer as a whole as

\begin{array}{l} (\binom{52}{13}) & = \frac{52!}{13! 39!} \\ = \frac{2^{49} \cdot 3^{23} \cdot 5^{12} \cdot 7^{8} \cdot 1 1^{4} \cdot 1 3^{4} \cdot 1 7^{3} \cdot 1 9^{2} \cdot 2 3^{2} \cdot 29 \cdot 31 \cdot 37 \cdot 41 \cdot 43 \cdot 47}{2^{10} \cdot 3^{5} \cdot 5^{2} \cdot 7 \cdot 11 \cdot 13 \cdot 2^{35} \cdot 3^{18} \cdot 5^{8} \cdot 7^{5} \cdot 1 1^{3} \cdot 1 3^{3} \cdot 1 7^{2} \cdot 1 9^{2} \cdot 23 \cdot 29 \cdot 31 \cdot 37} \\ = \frac{2^{49} \cdot 3^{23} \cdot 5^{12} \cdot 7^{8} \cdot 1 1^{4} \cdot 1 3^{4} \cdot 1 7^{3} \cdot 1 9^{2} \cdot 2 3^{2} \cdot 29 \cdot 31 \cdot 37 \cdot 41 \cdot 43 \cdot 47}{2^{45} \cdot 3^{23} \cdot 5^{10} \cdot 7^{6} \cdot 1 1^{4} \cdot 1 3^{4} \cdot 1 7^{2} \cdot 1 9^{2} \cdot 23 \cdot 29 \cdot 31 \cdot 37} \\ = 2^{4} \cdot 5^{2} \cdot 7^{2} \cdot 17 \cdot 23 \cdot 41 \cdot 43 \cdot 47 . \end{array}

By the binomial theorem,

\begin{array}{l} 1 1^{4} & = {(10 + 1)}^{4} \\ = \sum_{0 \leq k \leq 4} (\binom{4}{k}) 1 0^{k} 1^{4 - k} \\ = (\binom{4}{4}) 1 0^{4} + (\binom{4}{3}) 1 0^{3} + (\binom{4}{2}) 1 0^{2} + (\binom{4}{1}) 1 0^{1} + (\binom{4}{0}) 1 0^{0} \\ = (1) 1 0^{4} + (4) 1 0^{3} + (6) 1 0^{2} + (4) 1 0^{1} + (1) 1 0^{0} \\ = 14641 . \end{array}

That is, the digits represent the row in Pascal’s triangle for $(\binom{4}{k})$ , $0 \leq k \leq 4$ .

Using Eq. (9)

(\binom{r}{k}) = (\binom{r - 1}{k}) + (\binom{r - 1}{k - 1})

we can extend Pascal’s triangle (Table 1) for $r = - 1$ , $- 2$ , and $- 3$ as


$r$	$(\binom{r}{0})$	$(\binom{r}{1})$	$(\binom{r}{2})$	$(\binom{r}{3})$	$(\binom{r}{4})$	$(\binom{r}{5})$	$(\binom{r}{6})$	$(\binom{r}{7})$	$(\binom{r}{8})$	$(\binom{r}{9})$

-3	1	-3	6	-10	15	-21	28	-36	45	-55
-2	1	-2	3	-4	5	-6	7	-8	9	-10
-1	1	-1	1	-1	1	-1	1	-1	1	-1

since $(\binom{r}{0}) = 1$ , $(\binom{r}{1}) = r$ , and $(\binom{r - 1}{k}) = (\binom{r}{k}) - (\binom{r - 1}{k - 1})$ .

Proposition. $(\binom{n}{k}) \leq (\binom{n}{⌈ n ∕ 2 ⌉}) = (\binom{n}{⌊ n ∕ 2 ⌋})$ for all integers $n \geq 1$ , $k$ .

Proof. Let $n$ , $k$ be arbitrary integers such that $n \geq 1$ . We must show that

(\binom{n}{k}) \leq (\binom{n}{⌈ n ∕ 2 ⌉}) = (\binom{n}{⌊ n ∕ 2 ⌋}) .

First, we must show that the binomial coeﬃcient is monotone in $k$ , $0 \leq k \leq ⌈ \frac{n}{2} ⌉$ . That is, that

(\binom{n}{k - 1}) \leq (\binom{n}{k}) 1 \leq k \leq ⌈\frac{n}{2}⌉ .

But

\begin{array}{l} k \leq ⌈\frac{n}{2}⌉ & \Leftrightarrow k \leq \frac{n + 1}{2} \\ \Leftrightarrow 2 k \leq n + 1 \\ \Leftrightarrow k \leq n - k + 1 \\ \Leftrightarrow k \leq n - (k - 1) \\ \Leftrightarrow \frac{k}{n - (k - 1)} \leq 1 \\ \Leftrightarrow \frac{k}{n - (k - 1)} (\binom{n}{k}) \leq (\binom{n}{k}) \\ \Leftrightarrow \frac{k}{n - (k - 1)} \frac{n!}{k! (n - k)!} \leq (\binom{n}{k}) \\ \Leftrightarrow \frac{n!}{(k - 1)! (n - (k - 1))!} \leq (\binom{n}{k}) \\ \Leftrightarrow (\binom{n}{k - 1}) \leq (\binom{n}{k}) . \end{array}

And by deﬁnition, since $(\binom{n}{k}) = 0 < 1 = (\binom{n}{0})$ for $k < 0$ , we have in general that if $k \leq ⌈\frac{n}{2}⌉$

(\binom{n}{k - 1}) \leq (\binom{n}{k}),

or equivalently that if $k \leq ⌈\frac{n}{2}⌉$

(\binom{n}{k}) \leq (\binom{n}{⌈ n ∕ 2 ⌉}) .

In the case that $k > ⌈\frac{n}{2}⌉$ ,

\begin{array}{l} k > ⌈\frac{n}{2}⌉ & \Leftrightarrow - k < - ⌈\frac{n}{2}⌉ \\ \Leftrightarrow n - k < n - ⌈\frac{n}{2}⌉ \\ \Leftrightarrow n - k < n + ⌊\frac{- n}{2}⌋ \\ \Leftrightarrow n - k < ⌊n + \frac{- n}{2}⌋ \\ \Leftrightarrow n - k < ⌊\frac{n}{2}⌋ \end{array}

so that

(\binom{n}{k}) = (\binom{n}{n - k}) \leq (\binom{n}{⌊ n ∕ 2 ⌋}) = (\binom{n}{⌈ n ∕ 2 ⌉}) .

That is for all integers $n \geq 1$ and $k$

(\binom{n}{k}) \leq (\binom{n}{⌈ n ∕ 2 ⌉}) = (\binom{n}{⌊ n ∕ 2 ⌋})

as we needed to show. □

The property of Pascal’s triangle that is reﬂected in the “symmetry condition,” Eq. (6), is the symmetry of the triangle itself. That is, each row, not counting zeros, is palindromic: values read the same left to right and vice versa.

Since $(\binom{n}{n}) = (\binom{n}{0}) = 1$ and $(\binom{n}{k}) = 0$ for $k < 0$ , we have

(\binom{n}{n}) = \{\begin{matrix} 1 & if n \geq 0 \\ 0 & otherwise. \end{matrix}

The answers to exercise 10 follow below.

a)

We may prove the equivalence.

Proposition. $(\binom{n}{p}) \equiv ⌊\frac{n}{p}⌋ (\mod p)$ .

Proof. Let $n$ and $p$ be arbitrary integers such that $n \geq 1$ and $p$ prime. We must show that

(\binom{n}{p}) \equiv ⌊\frac{n}{p}⌋ (\mod p) .

But given (e) with $k = p$ ,

\begin{array}{l} (\binom{n}{p}) & \equiv (\binom{⌊ n ∕ p ⌋}{⌊ p ∕ p ⌋}) (\binom{n mod p}{p mod p}) \\ \equiv (\binom{⌊ n ∕ p ⌋}{1}) (\binom{n mod p}{0}) \\ \equiv (\binom{⌊ n ∕ p ⌋}{1}) \\ \equiv ⌊\frac{n}{p}⌋ (\mod p) \end{array}

as we needed to show. □

b)

We may prove the equivalence.

Proposition. $(\binom{p}{k}) \equiv 0 (\mod p)$ for $1 \leq k \leq p - 1$ .

Proof. Let $p$ and $k$ be arbitrary integers such that $p$ is prime and $1 \leq k \leq p - 1$ . We must show that

(\binom{p}{k}) \equiv 0 (\mod p) .

But given (e) with $n = p$ , and since $k ∕ p < 1$ ,

\begin{array}{l} (\binom{p}{k}) & \equiv (\binom{⌊ p ∕ p ⌋}{⌊ k ∕ p ⌋}) (\binom{p mod p}{k mod p}) \\ \equiv (\binom{1}{0}) (\binom{0}{k}) \\ \equiv 1 \cdot 0 \\ \equiv 0 (\mod p) \end{array}

as we needed to show. □

c)

We may prove the equivalence.

Proposition. $(\binom{p - 1}{k}) \equiv {(- 1)}^{k} (\mod p)$ for $0 \leq k \leq p - 1$ .

Proof. Let $p$ and $k$ be arbitrary integers such that $p$ is prime and $0 \leq k \leq p - 1$ . We must show that

(\binom{p - 1}{k}) \equiv {(- 1)}^{k} (\mod p) .

If $k = 0$ , then clearly

(\binom{p - 1}{0}) \equiv 1 \equiv {(- 1)}^{k} (\mod p) .

Then, assuming

(\binom{p - 1}{k}) \equiv {(- 1)}^{k} (\mod p),

we must show that

(\binom{p - 1}{k + 1}) \equiv {(- 1)}^{k + 1} (\mod p) .

But by the addition formula and (b),

\begin{array}{l} (\binom{p - 1}{k + 1}) & \equiv (\binom{p}{k + 1}) - (\binom{p - 1}{k}) \\ \equiv (\binom{p}{k + 1}) - {(- 1)}^{k} \\ \equiv 0 - {(- 1)}^{k} \\ \equiv {(- 1)}^{k + 1} (\mod p) \end{array}

as we needed to show. □

d)

We may prove the equivalence.

Proposition. $(\binom{p + 1}{k}) \equiv 0 (\mod p)$ for $2 \leq k \leq p - 1$ .

Proof. Let $p$ and $k$ be arbitrary integers such that $p$ is prime and $2 \leq k \leq p - 1$ . We must show that

(\binom{p + 1}{k}) \equiv 0 (\mod p) .

But by the addition formula Eq. (3) and (b),

\begin{array}{l} (\binom{p + 1}{k}) & \equiv (\binom{p}{k}) + (\binom{p}{k - 1}) \\ \equiv 0 + 0 \\ \equiv 0 (\mod p) \end{array}

as we needed to show. □

e)

We may prove the equivalence.

Proposition. $(\binom{n}{k}) \equiv (\binom{⌊n ∕ p⌋}{⌊k ∕ p⌋}) (\binom{n mod p}{k mod p}) (\mod p)$ .

Proof. Let $n$ , $k$ , and $p$ be arbitrary integers such that $p$ is prime. We must show that

(\binom{n}{k}) \equiv (\binom{⌊n ∕ p⌋}{⌊k ∕ p⌋}) (\binom{n mod p}{k mod p}) (\mod p) .

Note that

\begin{array}{l} n & = ⌊\frac{n}{p}⌋ p + (n mod p) & 0 \leq n mod p < p, \\ k & = ⌊\frac{k}{p}⌋ p + (k mod p) & 0 \leq k mod p < p . \end{array}

Also note from Eq. (7), that

s (\binom{r}{s}) = r (\binom{r - 1}{s - 1}),

with $r = p^{⌊n ∕ p⌋}$ and $s = k$ implies

(\binom{p^{⌊n ∕ p⌋}}{s}) \equiv 0 (\mod p)

and for arbitrary $x$ that

{(x + 1)}^{⌊n ∕ p⌋ p} \equiv {(x^{p} + 1)}^{⌊n ∕ p⌋} (\mod p) .

Then, for arbitrary $x$ by the binomial theorem,

\begin{array}{l} \sum_{0 \leq k \leq n} (\binom{n}{k}) x^{k} & = {(x + 1)}^{n} \\ = {(x + 1)}^{⌊n ∕ p⌋ p + (n mod p)} \\ = {(x + 1)}^{⌊n ∕ p⌋ p} {(x + 1)}^{n mod p} \\ \equiv {(x^{p} + 1)}^{⌊n ∕ p⌋} {(x + 1)}^{n mod p} (\mod p) \\ = (\sum_{0 \leq i \leq ⌊n ∕ p⌋} (\binom{⌊n ∕ p⌋}{i}) x^{i p}) (\sum_{0 \leq j \leq n mod p} (\binom{n mod p}{j}) x^{j}) \\ = \sum_{0 \leq i p + j \leq ⌊n ∕ p⌋ p + (n mod p)} (\binom{⌊n ∕ p⌋}{i}) (\binom{n mod p}{j}) x^{i p + j} \\ = \sum_{0 \leq k \leq n} (\binom{⌊n ∕ p⌋}{⌊k ∕ p⌋}) (\binom{n mod p}{k mod p}) x^{k}, \end{array}

or equivalently, by equating coeﬃcients

(\binom{n}{k}) \equiv (\binom{⌊n ∕ p⌋}{⌊k ∕ p⌋}) (\binom{n mod p}{k mod p}) (\mod p)

as we needed to show. □

f)

We may prove the equivalence.

Proposition. If $n = \sum_{0 \leq i \leq r} a_{i} p^{i}$ and $k = \sum_{0 \leq i \leq r} b_{i} p^{i}$ , then $(\binom{n}{k}) \equiv \prod_{0 \leq i \leq r} (\binom{a_{i}}{b_{i}}) (\mod p)$ .

Proof. Let $n$ , $k$ , and $p$ be arbitrary integers such that $n = \sum_{0 \leq i \leq r} a_{i} p^{i}$ and $k = \sum_{0 \leq i \leq r} b_{i} p^{i}$ are the $p$ -ary number representations of $n$ and $k$ with $r$ coeﬃcients $a_{i}$ , $b_{i}$ , respectively, $0 \leq i \leq r$ and $0 \leq a_{i}, b_{i} \leq p$ . We must show that

(\binom{n}{k}) \equiv \prod_{0 \leq i \leq r} (\binom{a_{i}}{b_{i}}) (mod p) .

If $r = 0$ , then $n = a_{0}$ and $k = b_{0}$ , and clearly,

\begin{array}{l} (\binom{n}{k}) & \equiv (\binom{a_{0}}{b_{0}}) \\ \equiv \prod_{0 \leq i \leq r} (\binom{a_{i}}{b_{i}}) (mod p) . \end{array}

Then, assuming for an arbitrary integer $r \geq 0$ with $n = \sum_{0 \leq i \leq r} a_{i} p^{i}$ and $k = \sum_{0 \leq i \leq r} b_{i} p^{i}$ that

(\binom{n}{k}) \equiv \prod_{0 \leq i \leq r} (\binom{a_{i}}{b_{i}}) (mod p),

we must show that

(\binom{n^{'}}{k^{'}}) \equiv \prod_{0 \leq i \leq r + 1} (\binom{a_{i}}{b_{i}}) (mod p)

for $n^{'} = a_{r + 1} p^{r + 1} + n = \sum_{0 \leq i \leq r + 1} a_{i} p^{i}$ and $k^{'} = b_{r + 1} p^{r + 1} + k = \sum_{0 \leq i \leq r + 1} b_{i} p^{i}$ .

But given (e)

\begin{array}{l} (\binom{n^{'}}{k^{'}}) & \equiv (\binom{⌊n^{'} ∕ p⌋}{⌊k^{'} ∕ p⌋}) (\binom{n^{'} mod p}{k^{'} mod p}) \\ \equiv (\binom{⌊\frac{1}{p} \sum_{0 \leq i \leq r + 1} a_{i} p^{i}⌋}{⌊\frac{1}{p} \sum_{0 \leq i \leq r + 1} b_{i} p^{i}⌋}) (\binom{\sum_{0 \leq i \leq r + 1} a_{i} p^{i} mod p}{\sum_{0 \leq i \leq r + 1} b_{i} p^{i} mod p}) \\ \equiv (\binom{⌊\sum_{0 \leq i \leq r + 1} a_{i} p^{i - 1}⌋}{⌊\sum_{0 \leq i \leq r + 1} b_{i} p^{i - 1}⌋}) (\binom{a_{0}}{b_{0}}) \\ \equiv (\binom{\sum_{1 \leq i \leq r + 1} a_{i} p^{i - 1}}{\sum_{1 \leq i \leq r + 1} b_{i} p^{i - 1}}) (\binom{a_{0}}{b_{0}}) \\ \equiv (\binom{\sum_{0 \leq i \leq r} a_{i + 1} p^{i}}{\sum_{0 \leq i \leq r} b_{i + 1} p^{i}}) (\binom{a_{0}}{b_{0}}) \\ \equiv (\binom{a_{0}}{b_{0}}) (\binom{\sum_{0 \leq i \leq r} a_{i + 1} p^{i}}{\sum_{0 \leq i \leq r} b_{i + 1} p^{i}}) \\ \equiv (\binom{a_{0}}{b_{0}}) \prod_{0 \leq i \leq r} (\binom{a_{i + 1}}{b_{i + 1}}) \\ \equiv (\binom{a_{0}}{b_{0}}) \prod_{1 \leq i \leq r + 1} (\binom{a_{i}}{b_{i}}) \\ \equiv \prod_{0 \leq i \leq r + 1} (\binom{a_{i}}{b_{i}}) (mod p) \end{array}

as we needed to show. □

______________________________________________________________________________________________________________________________

É. Lucas, American J. Math. 1 (1878), 229–230; L. E. Dickson, Quart. J. Math. 33 (1902), 383–384; N. J. Fine, AMM 54 (1947), 589–592.

Proposition. If $p$ is prime and $p^{n} ∣ (\binom{a + b}{a})$ but $p^{n + 1} ∤ (\binom{a + b}{a})$ , then $n$ is the number of carries that occur when $a$ is added to $b$ in the $p$ -ary number system.

Proof. Let $p$ , $n$ , $a$ , and $b$ be arbitrary nonnegative integers such that $p$ is prime,

p^{n} ∣ (\binom{a + b}{a}),

and

p^{n + 1} ∤ (\binom{a + b}{a}) .

We must show that $n$ is the number of carries that occur when $a$ is added to $b$ in the $p$ -ary number system. That is, given representations $a = \sum_{0 \leq k \leq r} a_{k} p^{k}$ , $b = \sum_{0 \leq k \leq r} b_{k} p^{k}$ , and $a + b = c = \sum_{0 \leq k \leq r} c_{k} p^{k}$ , that $n$ is zero for $a + b < p$ and increases by one for every additional carry.

But

\begin{array}{l} (\binom{a + b}{a}) & = (\binom{c}{a}) \\ = \frac{c!}{a! b!} \end{array}

and for $μ$ from exercise 1.2.5-12,

\begin{array}{l} p^{n} ∣ \frac{c!}{a! b!} & \Leftrightarrow \frac{p^{μ (c!)}}{p^{μ (a!)} p^{μ (b!)}} ∣ \frac{c!}{a! b!} \\ \Leftrightarrow p^{μ (c!) - μ (a!) - μ (b!)} ∣ \frac{c!}{a! b!} \\ \Leftrightarrow n = μ (c!) - μ (a!) - μ (b!) . \end{array}

Then,

\begin{array}{l} n & = μ (c!) - μ (a!) - μ (b!) \\ = \frac{c - \sum_{0 \leq k \leq r} c_{k}}{p - 1} - \frac{a - \sum_{0 \leq k \leq r} a_{k}}{p - 1} - \frac{b - \sum_{0 \leq k \leq r} b_{k}}{p - 1} \\ = \frac{c - (\sum_{0 \leq k \leq r} c_{k}) - a + (\sum_{0 \leq k \leq r} a_{k}) - b + (\sum_{0 \leq k \leq r} b_{k})}{p - 1} \\ = \frac{- \sum_{0 \leq k \leq r} c_{k} + \sum_{0 \leq k \leq r} a_{k} + \sum_{0 \leq k \leq r} b_{k}}{p - 1} \\ = \frac{\sum_{0 \leq k \leq r} a_{k} + b_{k} - c_{k}}{p - 1} . \end{array}

To see show that $n$ is the number of carries, we construct an inductive argument. As our basis, we consider $a + b < p$ , so that $r = 0$ , $a = a_{0} < p$ , $b = b_{0} < p$ , and $a + b = c = c_{0} < p$ . In this case, we have no carries, and $n$ is given by

n = \frac{\sum_{0 \leq k \leq r} a_{k} + b_{k} - c_{k}}{p - 1} = \frac{a_{0} + b_{0} - c_{0}}{p - 1} = 0,

as expected. Then, assuming $n$ is the number of carries for arbitrary $r$ and $a + b = c$ , we must show that $n^{'} = n + 1$ for $a + b = c^{'}$ given a single carry from digit $κ - 1$ to $κ$ as a result of the addition of $a_{k - 1} + b_{k - 1} \geq p$ , establishing the relation

c_{k}^{'} = \{\begin{matrix} c_{k} - p & if k = κ - 1 \\ c_{k} + 1 & if k = κ \\ c_{k} & otherwise. \end{matrix}

But

\begin{array}{l} n^{'} & = \frac{\sum_{0 \leq k \leq r} a_{k} + b_{k} - c_{k}^{'}}{p - 1} \\ = \frac{\sum_{\begin{array}{c} 0 \leq k \leq r \\ κ - 1 \leq k \leq κ \end{array}} a_{k} + b_{k} - c_{k}^{'} + \sum_{\begin{array}{c} 0 \leq k \leq r \\ k < κ - 1 \lor κ < k \end{array}} a_{k} + b_{k} - c_{k}^{'}}{p - 1} \\ = \frac{a_{κ - 1} + b_{κ - 1} - c_{κ - 1}^{'} + a_{κ} + b_{κ} - c_{κ}^{'} + \sum_{\begin{array}{c} 0 \leq k \leq r \\ k < κ - 1 \lor κ < k \end{array}} a_{k} + b_{k} - c_{k}^{'}}{p - 1} \\ = \frac{a_{κ - 1} + b_{κ - 1} - (c_{κ - 1} - p) + a_{κ} + b_{κ} - (c_{κ} + 1) + \sum_{\begin{array}{c} 0 \leq k \leq r \\ k < κ - 1 \lor κ < k \end{array}} a_{k} + b_{k} - c_{k}}{p - 1} \\ = \frac{p - 1 + a_{κ - 1} + b_{κ - 1} - c_{κ - 1} + a_{κ} + b_{κ} - c_{κ} + \sum_{\begin{array}{c} 0 \leq k \leq r \\ k < κ - 1 \lor κ < k \end{array}} a_{k} + b_{k} - c_{k}}{p - 1} \\ = \frac{p - 1 + \sum_{\begin{array}{c} 0 \leq k \leq r \\ κ - 1 \leq k \leq κ \end{array}} a_{k} + b_{k} - c_{k} + \sum_{\begin{array}{c} 0 \leq k \leq r \\ k < κ - 1 \lor κ < k \end{array}} a_{k} + b_{k} - c_{k}}{p - 1} \\ = \frac{p - 1 + \sum_{0 \leq k \leq r} a_{k} + b_{k} - c_{k}}{p - 1} \\ = \frac{\sum_{0 \leq k \leq r} a_{k} + b_{k} - c_{k}}{p - 1} + \frac{p - 1}{p - 1} \\ = n + 1 \end{array}

as we needed to show. □

______________________________________________________________________________________________________________________________

Knuth and Wilf, Crelle 396 (1989), 212–219.

We want to ﬁnd all positive integers $n$ such that if $(\binom{n}{k}) > 0$ , then $(\binom{n}{k}) \equiv 1 (\mod 2)$ . Let $k$ be an arbitrary integer such that $0 \leq k \leq n$ , and, from Eq. (3), so that $(\binom{n}{k}) > 0$ . We want to ﬁnd $n$ such that

(\binom{n}{k}) \equiv 1 (\mod 2) .

But, by exercise 1.2.6-10(f), given the binary representations $n = \sum_{0 \leq i \leq r} a_{i} 2^{i}$ and $k = \sum_{0 \leq i \leq r} b_{i} 2^{i}$ ,

\begin{array}{l} (\binom{n}{k}) & \equiv \prod_{0 \leq i \leq r} (\binom{a_{i}}{b_{i}}) \\ \equiv 1 (\mod 2) \end{array}

if and only if each $(\binom{a_{i}}{b_{i}}) = 1$ . Since for each $a_{i}$ and $b_{i}$ , $0 \leq a_{i}, b_{i} \leq 1$ , of the four cases, we require $b_{i} \leq a_{i}$ ; or equivalently, we require $a_{i} = 1$ unless $n = k = 0$ ; or

\begin{array}{l} n & = \sum_{0 \leq i \leq r} 2^{i} \\ = 2^{r + 1} - 1 . \end{array}

Hence, all the nonzero entries in the $n$ th row of Pascal’s triangle—those for which $0 \leq k \leq n$ —are odd if $n = 2^{m} - 1$ for some integer $m \geq 0$ . (This can be generalized to nondivisibility by a prime $p$ if $n = a p^{m} - 1$ for $1 \leq a < p$ .)

Proposition. $\sum_{0 \leq k \leq n} (\binom{r + k}{k}) = (\binom{r + n + 1}{n})$ .

Proof. Let $n$ and $r$ be arbitrary integers such that $n \geq 0$ . We must show that

\sum_{0 \leq k \leq n} (\binom{r + k}{k}) = (\binom{r + n + 1}{n}) .

If $n = 0$ , from Eq. (4),

\begin{array}{l} \sum_{0 \leq k \leq n} (\binom{r + k}{k}) & = \sum_{0 \leq k \leq 0} (\binom{r + k}{k}) \\ = (\binom{r + 0}{0}) \\ = (\binom{r}{0}) \\ = 1 \\ = (\binom{r + 0 + 1}{0}) \\ = (\binom{r + n + 1}{n}) . \end{array}

Then, assuming

\sum_{0 \leq k \leq n} (\binom{r + k}{k}) = (\binom{r + n + 1}{n}),

we must show that

\sum_{0 \leq k \leq n + 1} (\binom{r + k}{k}) = (\binom{r + n + 2}{n + 1}) .

But

\begin{array}{l} \sum_{0 \leq k \leq n + 1} (\binom{r + k}{k}) & = (\binom{r + n + 1}{n + 1}) + \sum_{0 \leq k \leq n} (\binom{r + k}{k}) \\ = (\binom{r + n + 1}{n + 1}) + (\binom{r + n + 1}{n}) \\ = \frac{(r + n + 1)!}{(n + 1)! r!} + \frac{(r + n + 1)!}{n! (r + 1)!} \\ = \frac{(r + 1) (r + n + 1)!}{(n + 1)! (r + 1)!} + \frac{(n + 1) (r + n + 1)!}{(n + 1)! (r + 1)!} \\ = \frac{(r + 1) (r + n + 1)! + (n + 1) (r + n + 1)!}{(n + 1)! (r + 1)!} \\ = \frac{(r + n + 2) (r + n + 1)!}{(n + 1)! (r + 1)!} \\ = \frac{(r + n + 2)!}{(n + 1)! (r + 1)!} \\ = (\binom{r + n + 2}{n + 1}) \end{array}

as we needed to show. □

For an arbitrary integer $k \geq 0$ ,

\begin{array}{l} k^{4} & = \sum_{0 \leq j \leq 4} \{\binom{4}{j}\} k^{\bar{j}} & from Eq. (45) \\ = \sum_{0 \leq j \leq 4} \{\binom{4}{j}\} j! (\binom{k}{j}) & from Eq. (3) \\ = 24 (\binom{k}{4}) + 36 (\binom{k}{3}) + 14 (\binom{k}{2}) + (\binom{k}{1}) . \end{array}

Summing over $k$ and from Eq. (11),

\begin{array}{l} \sum_{0 \leq k \leq n} k^{4} & = \sum_{0 \leq k \leq n} (24 (\binom{k}{4}) + 36 (\binom{k}{3}) + 14 (\binom{k}{2}) + (\binom{k}{1})) \\ = 24 \sum_{0 \leq k \leq n} (\binom{k}{4}) + 36 \sum_{0 \leq k \leq n} (\binom{k}{3}) + 14 \sum_{0 \leq k \leq n} (\binom{k}{2}) + \sum_{0 \leq k \leq n} (\binom{k}{1}) \\ = 24 (\binom{n + 1}{5}) + 36 (\binom{n + 1}{4}) + 14 (\binom{n + 1}{3}) + (\binom{n + 1}{2}) \\ = \frac{n^{5}}{5} + \frac{n^{4}}{2} + \frac{n^{3}}{3} - \frac{n}{30} \\ = \frac{1}{30} n (n + 1) (2 n + 1) (3 n^{2} + 3 n - 1) \\ = \frac{n (n + 1) (n + \frac{1}{2}) (3 n^{2} + 3 n - 1)}{15} . \end{array}

Proposition. ${(x + y)}^{r} = \sum_{0 \leq k \leq r} (\binom{r}{k}) x^{k} y^{r - k}$ .

Proof. Let $x$ , $y$ , and $r$ be arbitrary integers such that $r \geq 0$ . We must show that

{(x + y)}^{r} = \sum_{0 \leq k \leq r} (\binom{r}{k}) x^{k} y^{r - k} .

If $r = 0$ , then clearly

\begin{array}{l} {(x + y)}^{r} & = {(x + y)}^{0} \\ = 1 \\ = (\binom{0}{0}) x^{0} y^{0} \\ = \sum_{0 \leq k \leq r} (\binom{r}{k}) x^{k} y^{r - k} . \end{array}

Then, assuming

{(x + y)}^{r} = \sum_{0 \leq k \leq r} (\binom{r}{k}) x^{k} y^{r - k},

we must show that

{(x + y)}^{r + 1} = \sum_{0 \leq k \leq r + 1} (\binom{r + 1}{k}) x^{k} y^{r + 1 - k} .

But

\begin{array}{l} {(x + y)}^{r + 1} & = (x + y) {(x + y)}^{r} \\ = (x + y) \sum_{0 \leq k \leq r} (\binom{r}{k}) x^{k} y^{r - k} \\ = x \sum_{0 \leq k \leq r} (\binom{r}{k}) x^{k} y^{r - k} + y \sum_{0 \leq k \leq r} (\binom{r}{k}) x^{k} y^{r - k} \\ = \sum_{0 \leq k \leq r} (\binom{r}{k}) x^{k + 1} y^{r - k} + \sum_{0 \leq k \leq r} (\binom{r}{k}) x^{k} y^{r + 1 - k} \\ = \sum_{0 \leq k - 1 \leq r} (\binom{r}{k - 1}) x^{k} y^{r + 1 - k} + \sum_{0 \leq k \leq r} (\binom{r}{k}) x^{k} y^{r + 1 - k} \\ = \sum_{1 \leq k \leq r + 1} (\binom{r}{k - 1}) x^{k} y^{r + 1 - k} + \sum_{0 \leq k \leq r} (\binom{r}{k}) x^{k} y^{r + 1 - k} \\ = \sum_{0 \leq k \leq r + 1} (\binom{r}{k - 1}) x^{k} y^{r + 1 - k} + \sum_{0 \leq k \leq r + 1} (\binom{r}{k}) x^{k} y^{r + 1 - k} \\ = \sum_{0 \leq k \leq r + 1} (\binom{r + 1}{k}) x^{k} y^{r + 1 - k} & from Eq. (9) \end{array}

as we needed to show. □

Proposition. ${(- 1)}^{n} (\binom{- n}{k - 1}) = {(- 1)}^{k} (\binom{- k}{n - 1})$ .

Proof. Let $n$ and $k$ be arbitrary positive integers. We must show that

{(- 1)}^{n} (\binom{- n}{k - 1}) = {(- 1)}^{k} (\binom{- k}{n - 1}) .

But

\begin{array}{l} {(- 1)}^{n} (\binom{- n}{k - 1}) & = {(- 1)}^{n} {(- 1)}^{k - 1} (\binom{k - 1 + n - 1}{k - 1}) & from Eq. (17) \\ = {(- 1)}^{n + k - 1} (\binom{n + k - 2}{k - 1}) \\ = {(- 1)}^{k} {(- 1)}^{n - 1} (\binom{n - 1 + k - 1}{k - 1}) \\ = {(- 1)}^{k} {(- 1)}^{n - 1} (\binom{n - 1 + k - 1}{n - 1 + k - 1 - (k - 1)}) & from Eq. (6) \\ = {(- 1)}^{k} {(- 1)}^{n - 1} (\binom{n - 1 + k - 1}{n - 1}) \\ = {(- 1)}^{k} (\binom{- k}{n - 1}) & from Eq. (17) \end{array}

as we needed to show. □

Proposition. $\sum_{0 \leq k \leq r} (\binom{r}{k}) (\binom{s}{n - k}) = (\binom{r + s}{n})$ .

Proof. Let $r$ and $s$ be arbitrary positive integers. We must show that

\sum_{0 \leq k \leq r} (\binom{r}{k}) (\binom{s}{n - k}) = (\binom{r + s}{n})

from Eq. (15)

\sum_{0 \leq k \leq r} (\binom{r}{k}) x^{k} = {(1 + x)}^{r}

and from the identity

{(1 + x)}^{r + s} = {(1 + x)}^{r} {(1 + x)}^{s} .

But

\begin{array}{l} \sum_{0 \leq n \leq r + s} (\binom{r + s}{n}) x^{n} & = {(1 + x)}^{r + s} \\ = {(1 + x)}^{r} {(1 + x)}^{s} \\ = \sum_{0 \leq k \leq r} (\binom{r}{k}) x^{k} \sum_{0 \leq k \leq s} (\binom{s}{k}) x^{k} \\ = \sum_{0 \leq k \leq r} (\binom{r}{k}) x^{k} \sum_{0 \leq n - k \leq s} (\binom{s}{n - k}) x^{n - k} \\ = \sum_{0 \leq n \leq r + s} (\sum_{0 \leq k \leq r} (\binom{r}{k}) (\binom{s}{n - k})) x^{n} . \end{array}

Equating coeﬃcients yields

(\binom{r + s}{n}) = \sum_{0 \leq k \leq r} (\binom{r}{k}) (\binom{s}{n - k})

as we needed to show. □

Proposition. $\sum_{k} (\binom{r}{m + k}) (\binom{s}{n + k}) = (\binom{r + s}{r - m + n})$ .

Proof. Let $m$ , $n$ , $r$ , and $s$ be arbitrary integers such that $r \geq 0$ . We must show that

\sum_{k} (\binom{r}{m + k}) (\binom{s}{n + k}) = (\binom{r + s}{r - m + n}) .

But

\begin{array}{l} \sum_{k} (\binom{r}{m + k}) (\binom{s}{n + k}) & = \sum_{k - m} (\binom{r}{m + k - m}) (\binom{s}{n + k - m}) \\ = \sum_{k} (\binom{r}{k}) (\binom{s}{n + k - m}) \\ = \sum_{k} (\binom{r}{k}) (\binom{s}{k + n - m}) \\ = \sum_{k} (\binom{r}{k}) (\binom{s}{s - k + m - n}) & from Eq. (6) \\ = (\binom{r + s}{r + s - r + m - n}) & from Eq. (21) \\ = (\binom{r + s}{r - m + n}) & from Eq. (6) \end{array}

as we needed to show. □

Proposition. $\sum_{k} (\binom{r}{k}) (\binom{s + k}{n}) {(- 1)}^{r - k} = (\binom{s}{n - r})$ for integers $n$ , $r \geq 0$ .

Proof. Let $n$ , $r$ , and $s$ be arbitrary integers such that $r \geq 0$ . We must show that

\sum_{k} (\binom{r}{k}) (\binom{s + k}{n}) {(- 1)}^{r - k} = (\binom{s}{n - r}) .

If $r = 0$

\begin{array}{l} \sum_{k} (\binom{r}{k}) (\binom{s + k}{n}) {(- 1)}^{r - k} & = \sum_{k} (\binom{0}{k}) (\binom{s + k}{n}) {(- 1)}^{- k} \\ = (\binom{0}{0}) (\binom{s + 0}{n}) {(- 1)}^{0} \\ = (\binom{s}{n}) \\ = (\binom{s}{n - r}) . \end{array}

Then, assuming

\sum_{k} (\binom{r}{k}) (\binom{s + k}{n}) {(- 1)}^{r - k} = (\binom{s}{n - r}),

we must show that

\sum_{k} (\binom{r + 1}{k}) (\binom{s + k}{n}) {(- 1)}^{r + 1 - k} = (\binom{s}{n - r - 1}) .

But

\begin{array}{l} \sum_{k} (\binom{r + 1}{k}) (\binom{s + k}{n}) {(- 1)}^{r + 1 - k} \\ = \sum_{k} ((\binom{r}{k}) + (\binom{r}{k - 1})) (\binom{s + k}{n}) {(- 1)}^{r + 1 - k} \\ = \sum_{k} (\binom{r}{k}) (\binom{s + k}{n}) {(- 1)}^{r + 1 - k} + \sum_{k} (\binom{r}{k - 1}) (\binom{s + k}{n}) {(- 1)}^{r + 1 - k} \\ = - \sum_{k} (\binom{r}{k}) (\binom{s + k}{n}) {(- 1)}^{r - k} + \sum_{k + 1} (\binom{r}{k}) (\binom{s + k + 1}{n}) {(- 1)}^{r - k} \\ = - \sum_{k} (\binom{r}{k}) (\binom{s + k}{n}) {(- 1)}^{r - k} + \sum_{k} (\binom{r}{k}) (\binom{s + k + 1}{n}) {(- 1)}^{r - k} \\ = - (\binom{s}{n - r}) + (\binom{s + 1}{n - r}) \\ = (\binom{s + 1}{n - r}) - (\binom{s}{n - r}) \\ = \frac{s + 1}{s + 1 - (n - r)} (\binom{s}{n - r}) - (\binom{s}{n - r}) \\ = (\frac{s + 1}{s + 1 - (n - r)} - 1) (\binom{s}{n - r}) \\ = (\frac{n - r}{s + 1 - n + r}) (\binom{s}{n - r}) \\ = \frac{n - r}{s - n + r + 1} \frac{s!}{(n - r)! (s - n + r)!} \\ = \frac{s!}{(n - r - 1)! (s - n + r + 1)!} \\ = (\binom{s}{n - r - 1}) \end{array}

as we needed to show. □

We may prove Eq. (24) using Eqs. (19) and (21).

Proposition. $\sum_{0 \leq k \leq r} (\binom{r - k}{m}) (\binom{s}{k - t}) {(- 1)}^{k - t} = (\binom{r - t - s}{r - t - m})$ for nonnegative integers $t$ , $r$ , and $m$ .

Proof. Let $r$ , $m$ , $s$ , and $t$ be arbitrary integers such that $r, m, t \geq 0$ . We must show that

\sum_{0 \leq k \leq r} (\binom{r - k}{m}) (\binom{s}{k - t}) {(- 1)}^{k - t} = (\binom{r - t - s}{r - t - m}) .

But

\begin{array}{l} \sum_{0 \leq k \leq r} (\binom{r - k}{m}) (\binom{s}{k - t}) {(- 1)}^{k - t} & = \sum_{0 \leq k \leq r} {(- 1)}^{r - k - m} (\binom{- (m + 1)}{r - k - m}) (\binom{s}{k - t}) {(- 1)}^{k - t} & from Eq. (19) \\ = \sum_{0 \leq k \leq r} {(- 1)}^{r - m - t} (\binom{- (m + 1)}{r - k - m}) (\binom{s}{k - t}) \\ = {(- 1)}^{r - m - t} \sum_{0 \leq k \leq r} (\binom{- (m + 1)}{r - k - m}) (\binom{s}{k - t}) \\ = {(- 1)}^{r - m - t} \sum_{- t \leq k - t \leq r - t} (\binom{- (m + 1)}{r - k - t - m}) (\binom{s}{k}) \\ = {(- 1)}^{r - t - m} \sum_{k} (\binom{s}{k}) (\binom{- (m + 1)}{r - t - m - k}) \\ = {(- 1)}^{r - t - m} (\binom{s - m - 1}{r - t - m}) & from Eq. (21) \\ = {(- 1)}^{r - t - m} (\binom{r - t - m - r + t + s - 1}{r - t - m}) \\ = (\binom{r - t - s}{r - t - m}) & from Eq. (17) \end{array}

as we needed to show. □

We may also show that another use of Eq. (19) yields Eq. (25).

Proposition. $\sum_{0 \leq k \leq r} (\binom{r - k}{m}) (\binom{s + k}{n}) = (\binom{r + s + 1}{m + n + 1})$ for nonnegative integers $m$ , $n$ , $r$ , and $s$ .

Proof. Let $m$ , $n$ , $r$ , and $s$ be arbtirary nonnegative integers. We must show that

\sum_{0 \leq k \leq r} (\binom{r - k}{m}) (\binom{s + k}{n}) = (\binom{r + s + 1}{m + n + 1}) .

But

\begin{array}{l} \sum_{0 \leq k \leq r} (\binom{r - k}{m}) (\binom{s + k}{n}) & = \sum_{0 \leq k \leq r} (\binom{r - k}{m}) {(- 1)}^{s + k - n} (\binom{- (n + 1)}{s + k - n}) & from Eq. (19) \\ = \sum_{0 \leq k \leq r} (\binom{r - k}{m}) (\binom{- (n + 1)}{k - (n - s)}) {(- 1)}^{k - (n - s)} \\ = (\binom{r - (n - s) + n + 1}{r - (n - s) - m}) & from Eq. (24) \\ = (\binom{r + s + 1}{r + s + 1 - m - n - 1}) \\ = (\binom{r + s + 1}{m + n + 1}) & from Eq. (6) \end{array}

as we needed to show. □

According to the text on page 57, any polynomial $\sum_{0 \leq k \leq d} a_{k} s^{k}$ can be expressed as $\sum_{0 \leq k \leq d} b_{k} (\binom{s}{k})$ for suitably chosen coeﬃcients $b_{0}, b_{1}, \dots, b_{d}$ .

And so, the left hand of Eq. (25) can be expressed as

\sum_{0 \leq k \leq r} (\binom{r - k}{m}) (\binom{s + k}{n}) = \sum_{0 \leq k \leq n} a_{k} s^{k};

that is, a polynomial of degree at most $n$ for suitably chosen coeﬃcients $a_{0}, a_{1}, \dots, a_{n}$ ; and the right hand of Eq. (25) can be expressed as

(\binom{r + s + 1}{m + n + 1}) = \sum_{0 \leq k \leq m + n + 1} a_{k}^{'} s^{k};

that is, a polynomial of degree at most $m + n + 1$ for suitably chosen coeﬃcients $a_{0}^{'}, a_{1}^{'}, \dots, a_{m + n + 1}^{'}$ .

Therefore, even though both sides of Eq. (25) are polynomials in $s$ , since they do not agree at all $m + n + 1$ possible points, the equation does not serve as an identity in $s$ .

Proposition. $\sum_{0 \leq k} (\binom{r - t k}{k}) (\binom{n - 1 - (r - t k)}{n - k}) \frac{r}{r - t k} = (\binom{n - 1}{n})$ for integers $n$ .

Proof. Let $r$ , $t$ , and $n$ be arbtirary integers. We must show that

\sum_{0 \leq k} (\binom{r - t k}{k}) (\binom{n - 1 - (r - t k)}{n - k}) \frac{r}{r - t k} = (\binom{n - 1}{n}) .

We consider two cases, depending on whether $k \leq r - t k$ or not.

Case 1. [ $k \leq r - t k$ ] In the case that $k \leq r - t k$ ,

\begin{array}{l} k \leq r - t k & \Rightarrow - (r - t k) \leq - k \\ \Rightarrow n - (r - t k) \leq n - k \\ \Rightarrow n - 1 - (r - t k) < n - k \\ \Rightarrow (\binom{n - 1 - (r - t k)}{n - k}) = 0 \end{array}

which gives us that

\sum_{0 \leq k} (\binom{r - t k}{k}) (\binom{n - 1 - (r - t k)}{n - k}) \frac{r}{r - t k} = 0 = (\binom{n - 1}{n})

in this case.

Case 2. [ $k > r - t k$ ] In the case that $k > r - t k$ , clearly

\begin{array}{l} r - t k < k & \Rightarrow (\binom{r - t k}{k}) = 0 \end{array}

which gives us that

\sum_{0 \leq k} (\binom{r - t k}{k}) (\binom{n - 1 - (r - t k)}{n - k}) \frac{r}{r - t k} = 0 = (\binom{n - 1}{n})

in this case.

Therefore, in either case, we have that

\sum_{0 \leq k} (\binom{r - t k}{k}) (\binom{n - 1 - (r - t k)}{n - k}) \frac{r}{r - t k} = 0 = (\binom{n - 1}{n})

as we needed to show. □

Proposition. If $\sum_{0 \leq k} (\binom{r - t k}{k}) (\binom{s - t (n - k)}{n - k}) \frac{r}{r - t k} = (\binom{r - s - t n}{n})$ and $\sum_{0 \leq k} (\binom{r - t k}{k}) (\binom{s - t (n - k)}{n - k - 1}) \frac{r}{r - t k} = (\binom{r - s - t n}{n - 1})$ , then $\sum_{0 \leq k} (\binom{r - t k}{k}) (\binom{s - t (n - k) + 1}{n - k}) \frac{r}{r - t k} = (\binom{r - s - t n + 1}{n})$ .

Proof. Let $r$ , $s$ , $t$ , and $n$ be arbitrary integers such that

\sum_{0 \leq k} (\binom{r - t k}{k}) (\binom{s - t (n - k)}{n - k}) \frac{r}{r - t k} = (\binom{r - s - t n}{n})

and

\sum_{0 \leq k} (\binom{r - t k}{k}) (\binom{s - t (n - k)}{n - k - 1}) \frac{r}{r - t k} = (\binom{r - s - t n}{n - 1}) .

We must show that

\sum_{0 \leq k} (\binom{r - t k}{k}) (\binom{s - t (n - k) + 1}{n - k}) \frac{r}{r - t k} = (\binom{r - s - t n + 1}{n}) .

But

\begin{array}{l} \sum_{0 \leq k} (\binom{r - t k}{k}) (\binom{s - t (n - k) + 1}{n - k}) \frac{r}{r - t k} \\ = \sum_{0 \leq k} (\binom{r - t k}{k}) ((\binom{s - t (n - k)}{n - k}) + (\binom{s - t (n - k)}{n - k - 1})) \frac{r}{r - t k} \\ = \sum_{0 \leq k} (\binom{r - t k}{k}) (\binom{s - t (n - k)}{n - k}) \frac{r}{r - t k} + \sum_{0 \leq k} (\binom{r - t k}{k}) (\binom{s - t (n - k)}{n - k - 1}) \frac{r}{r - t k} \\ = (\binom{r - s - t n}{n}) + (\binom{r - s - t n}{n - 1}) \\ = (\binom{r - s - t n + 1}{n}) \end{array}

as we needed to show. □

The results of the previous two exercises combine to give a proof of Eq. (26) as a proof by induction on $n$ .

In the case that $n < 0$ ,

\begin{array}{l} \sum_{0 \leq k} (\binom{r - t k}{k}) (\binom{s - t (n - k)}{n - k}) \frac{r}{r - t k} & = 0 \\ = (\binom{r + s - t n}{n}); \end{array}

and in the case that $n = 0$ ,

\begin{array}{l} \sum_{0 \leq k} (\binom{r - t k}{k}) (\binom{s - t (n - k)}{n - k}) \frac{r}{r - t k} & = (\binom{r}{0}) (\binom{s}{0}) \frac{r}{r} \\ = 1 \\ = (\binom{r + s}{0}) \\ = (\binom{r + s - t n}{n}) . \end{array}

Otherwise, in the case that $n > 0$ , we may construct a proof by induction on $m \geq - 1$ with $s = n - r + n t + m$ . If $m = - 1$ ,

\begin{array}{l} \sum_{0 \leq k} (\binom{r - t k}{k}) (\binom{s - t (n - k)}{n - k}) \frac{r}{r - t k} \\ = \sum_{0 \leq k} (\binom{r - t k}{k}) (\binom{n - r + n t + m - t (n - k)}{n - k}) \frac{r}{r - t k} \\ = \sum_{0 \leq k} (\binom{r - t k}{k}) (\binom{n - 1 - r + n t - t (n - k)}{n - k}) \frac{r}{r - t k} \\ = \sum_{0 \leq k} (\binom{r - t k}{k}) (\binom{n - 1 - (r - t k)}{n - k}) \frac{r}{r - t k} \\ = (\binom{n - 1}{n}) & by exercise 22 \\ = (\binom{n + m}{n}) \\ = (\binom{r + n - r + n t + m - t n}{n}) \\ = (\binom{r + s - t n}{n}) . \end{array}

Then, assuming

\sum_{0 \leq k} (\binom{r - t k}{k}) (\binom{s - t (n - k)}{n - k}) \frac{r}{r - t k} = (\binom{r - s - t n}{n})

and

\sum_{0 \leq k} (\binom{r - t k}{k}) (\binom{s - t (n - k)}{n - k - 1}) \frac{r}{r - t k} = (\binom{r - s - t n}{n - 1}),

we must show that

\sum_{0 \leq k} (\binom{r - t k}{k}) (\binom{s - t (n - k) + 1}{n - k}) \frac{r}{r - t k} = (\binom{r - s - t n + 1}{n}) .

But, by exercise 24

\sum_{0 \leq k} (\binom{r - t k}{k}) (\binom{s - t (n - k) + 1}{n - k}) \frac{r}{r - t k} = (\binom{r - s - t n + 1}{n})

and hence the result.

Proposition. $\sum_{k} A_{k} (r, t) z^{k} = x^{r}$ for $z = x^{t + 1} - x^{t}$ suﬃciently small.

Proof. Let $A_{n} (x, t)$ be the $n$ th degree polynomial in $x$ that satisﬁes

A_{n} (x, t) = (\binom{x - n t}{n}) \frac{x}{x - n t}

for $x \neq n t$ ; and $z = x^{t + 1} - x^{t}$ suﬃciently small. We must show that

\sum_{j} A_{j} (r, t) z^{j} = x^{r} .

We may ﬁrst prove that the sum converges by using the ratio test; that is, that

\lim_{k \to \infty} |\frac{A_{k + 1} (r, t) z^{k + 1}}{A_{k} (r, t) z^{k}}| < 1 .

But if $z$ is suﬃciently small, $|z| \leq 1 ∕ t$ , or equivalently, $|- t z| < 1$ , then

\begin{array}{l} 1 & > |- t z| \\ = \lim_{k \to \infty} |\frac{(r - k t)}{(k + 1)} z| \\ = \lim_{k \to \infty} |\prod_{1 \leq j \leq k} \frac{(r - k t) (r - (k + 1) t) (r - k t + 1 - j)}{(r - (k + 1) t) (k + 1) (r - k t + 1 - j)} z| \\ \geq \lim_{k \to \infty} |\prod_{1 \leq j \leq k} \frac{(r - k t) (r - (k + 1) t - k) (r - (k + 1) t + 1 - j)}{(r - (k + 1) t) (k + 1) (r - k t + 1 - j)} z| \\ = \lim_{k \to \infty} |\frac{(r - k t) z (r - (k + 1) t - k) \prod_{1 \leq j \leq k} (r - (k + 1) t + 1 - j)}{(r - (k + 1) t) (k + 1) \prod_{1 \leq j \leq k} (r - k t + 1 - j)}| \\ = \lim_{k \to \infty} |\frac{(r - k t) z \frac{r - (k + 1) t - k}{k + 1} \prod_{1 \leq j \leq k} \frac{r - (k + 1) t + 1 - j}{j}}{(r - (k + 1) t) \prod_{1 \leq j \leq k} \frac{r - k t + 1 - j}{j}}| \\ = \lim_{k \to \infty} |\frac{(r - k t) z \prod_{1 \leq j \leq k + 1} \frac{r - (k + 1) t + 1 - j}{j}}{(r - (k + 1) t) \prod_{1 \leq j \leq k} \frac{r - k t + 1 - j}{j}}| \\ = \lim_{k \to \infty} |\frac{(\binom{r - (k + 1) t}{k + 1}) (r - k t) z}{(\binom{r - k t}{k}) (r - (k + 1) t)}| \\ = \lim_{k \to \infty} |\frac{(\binom{r - (k + 1) t}{k + 1}) \frac{r}{r - (k + 1) t} z}{(\binom{r - k t}{k}) \frac{r}{r - k t}}| \\ = \lim_{k \to \infty} |\frac{A_{k + 1} (r, t) z}{A_{k} (r, t)}| \\ = \lim_{k \to \infty} |\frac{A_{k + 1} (r, t) z^{k + 1}}{A_{k} (r, t) z^{k}}| \end{array}

and hence the proof of convergence.

Then, given the identity

\sum_{j} {(- 1)}^{j} (\binom{k}{j}) (\binom{r - j t}{k}) \frac{r}{r - j t} = δ_{k 0},

and letting $x = 1 ∕ (1 + w)$ so that $z = - w ∕ {(1 + w)}^{t + 1} = x^{t + 1} - x^{t}$ , we have that

\begin{array}{l} 1 & = δ_{00} \\ = \sum_{k} δ_{k 0} w^{k} \\ = \sum_{k} \sum_{j} {(- 1)}^{j} (\binom{k}{j}) (\binom{r - j t}{k}) \frac{r}{r - j t} w^{k} \\ = \sum_{j} {(- 1)}^{j} \frac{r}{r - j t} \sum_{k} (\binom{k}{j}) (\binom{r - j t}{k}) w^{k} \\ = \sum_{j} {(- 1)}^{j} \frac{r}{r - j t} \sum_{k} (\binom{r - j t}{j}) (\binom{r - j t - j}{k - j}) w^{k} & from Eq. (2) \\ = \sum_{j} {(- 1)}^{j} (\binom{r - j t}{j}) \frac{r}{r - j t} \sum_{k} (\binom{r - j t - j}{k - j}) w^{k} \\ = \sum_{j} {(- 1)}^{j} A_{j} (r, t) \sum_{k} (\binom{r - j t - j}{k - j}) w^{k} \\ = \sum_{j} {(- 1)}^{j} A_{j} (r, t) \sum_{k} (\binom{r - j t - j}{k - j}) w^{k - j} w^{j} \\ = \sum_{j} {(- 1)}^{j} A_{j} (r, t) {(1 + w)}^{r - j t - j} w^{j} \\ = \sum_{j} {(- 1)}^{j} A_{j} (r, t) {(1 ∕ x)}^{r - j t - j} {(1 ∕ x - 1)}^{j} \\ = \sum_{j} A_{j} (r, t) {(- 1)}^{j} {(1 ∕ x)}^{r - j t - j} {(1 ∕ x - 1)}^{j} \\ = \sum_{j} A_{j} (r, t) {(- 1)}^{j} {(1 ∕ x - 1)}^{j} {(1 ∕ x)}^{r - j t - j} \\ = \sum_{j} A_{j} (r, t) {(- 1)}^{j} {(1 ∕ x - 1)}^{j} {(1 ∕ x)}^{- j t - j} {(1 ∕ x)}^{r} \\ = \sum_{j} A_{j} (r, t) {(- (1 ∕ x - 1))}^{j} {({(1 ∕ x)}^{- t - 1})}^{j} {(1 ∕ x)}^{r} \\ = \sum_{j} A_{j} (r, t) {((1 - 1 ∕ x) x^{t + 1})}^{j} {(1 ∕ x)}^{r} \\ = \sum_{j} A_{j} (r, t) {(x^{t + 1} - x^{t})}^{j} {(1 ∕ x)}^{r} \\ = \sum_{j} A_{j} (r, t) z^{j} {(1 ∕ x)}^{r}; \end{array}

or equivalently, that

\sum_{j} A_{j} (r, t) z^{j} = x^{r}

as we needed to show. □

______________________________________________________________________________________________________________________________

H. W. Gould, AMM 63 (1956), 84–91.

Proposition. $\sum_{k} (\binom{r - t k}{k}) z^{k} = \frac{x^{r + 1}}{(t + 1) x - t}$ .

Proof. Let $A_{n} (x, t)$ be the $n$ th degree polynomial in $x$ from exercise 25 that satisﬁes

A_{n} (x, t) = (\binom{x - n t}{n}) \frac{x}{x - n t}

for $x \neq n t$ ; and $z = x^{t + 1} - x^{t}$ suﬃciently small so that $|z| \leq 1 ∕ t$ . We must show that

\sum_{k} (\binom{r - t k}{k}) z^{k} = \frac{x^{r + 1}}{(t + 1) x - t} .

From exercise 25, we have that $\sum_{k} A_{k} (r, t) z^{k} = x^{r}$ , or equivalently that

\begin{array}{l} 1 & = \sum_{k} A_{k} (r, t) z^{k} x^{- r} \\ = \sum_{k} A_{k} (r, t) {(x^{t + 1} - x^{t})}^{k} x^{- r} \\ = \sum_{k} A_{k} (r, t) x^{t k - r} {(x - 1)}^{k}; \end{array}

we have by deﬁnition that

\begin{array}{l} 1 & = \frac{d z}{d z} \\ = \frac{d}{d z} (x^{t + 1} - x^{t}) \\ = ((t + 1) x^{t} - t x^{t - 1}) \frac{d x}{d z} \\ = x^{t - 1} ((t + 1) x - t) \frac{d x}{d z} \end{array}

or equivalently that

\frac{d x}{d z} = \frac{x}{x^{t} ((t + 1) x - t)};

and we also have that $\frac{d}{d z} \sum_{k} A_{k} (r, t) z^{k} = \sum_{k} k A_{k} (r, t) z^{k - 1} = \frac{d (x^{r})}{d z}$ , or equivalently that

\begin{array}{l} \sum_{k} k A_{k} (r, t) z^{k} & = z \frac{d (x^{r})}{d z} \\ = (x^{t + 1} - x^{t}) r x^{r - 1} \frac{d x}{d z} \\ = (x^{t + 1} - x^{t}) r x^{r - 1} \frac{x}{x^{t} ((t + 1) x - t)} \\ = r x^{r - 1} (\frac{x^{2}}{(t + 1) x - t} - \frac{x}{(t + 1) x - t}) \\ = r x^{r} \frac{x - 1}{(t + 1) x - t} . \end{array}

Finally, diﬃrentiating the ﬁrst equality yields

\begin{array}{l} \frac{d}{d x} 1 & = 0 \\ = \frac{d}{d x} (\sum_{k} A_{k} (r, t) x^{t k - r} {(x - 1)}^{k}) \\ = \sum_{k} A_{k} (r, t) ({(x - 1)}^{k} (t k - r) (x^{t k - r - 1}) + x^{t k - r} k {(x - 1)}^{k - 1}) \\ = \sum_{k} A_{k} (r, t) ((t k - r) (x^{- r - 1}) + x^{- r} k {(x - 1)}^{- 1}) {(x - 1)}^{k} x^{t k} \\ = \sum_{k} A_{k} (r, t) ((t k - r) (x^{- r - 1}) + x^{- r} k {(x - 1)}^{- 1}) z^{k} \\ = \sum_{k} (t k - r) (x^{- r - 1}) A_{k} (r, t) z^{k} + \sum_{k} x^{- r} k {(x - 1)}^{- 1} A_{k} (r, t) z^{k} \\ = \sum_{k} (t k - r) (x^{- r - 1}) (\binom{r - k t}{k}) \frac{r}{r - k t} z^{k} + \sum_{k} x^{- r} k {(x - 1)}^{- 1} A_{k} (r, t) z^{k} \\ = \sum_{k} (- r) (x^{- r - 1}) (\binom{r - k t}{k}) z^{k} + \sum_{k} x^{- r} k {(x - 1)}^{- 1} A_{k} (r, t) z^{k} \\ = - r x^{- 1} \sum_{k} (\binom{r - k t}{k}) z^{k} + {(x - 1)}^{- 1} \sum_{k} k A_{k} (r, t) z^{k} \\ = - r x^{- 1} \sum_{k} (\binom{r - k t}{k}) z^{k} + {(x - 1)}^{- 1} r x^{r} \frac{x - 1}{(t + 1) x - t} \\ = - r x^{- 1} \sum_{k} (\binom{r - k t}{k}) z^{k} + \frac{r x^{r}}{(t + 1) x - t} \end{array}

if and only if

\begin{array}{l} \sum_{k} (\binom{r - k t}{k}) z^{k} & = \frac{x}{r} \frac{r x^{r}}{(t + 1) x - t} \\ = \frac{x^{r + 1}}{(t + 1) x - t} \end{array}

as we needed to show. □

We may solve Example 4 from the text using the result of exercise 25.

Proposition. $\sum_{k} A_{k} (r, t) A_{n - k} (s, t) = A_{n} (r + s, t)$ for nonnegative integers $n$ .

Proof. Let $A_{n} (x, t)$ be the $n$ th degree polynomial in $x$ from exercise 25 that satisﬁes

A_{n} (x, t) = (\binom{x - n t}{n}) \frac{x}{x - n t}

for $x \neq n t$ ; and $z = x^{t + 1} - x^{t}$ suﬃciently small so that $|z| \leq 1 ∕ t$ . We must show that

\sum_{k} A_{k} (r, t) A_{n - k} (s, t) = A_{n} (r + s, t) .

From exercise 25, we have that $\sum_{n} A_{n} (r + s, t) z^{n} = x^{r + s}$ . And so,

\begin{array}{l} \sum_{n} \sum_{k} A_{k} (r, t) A_{n - k} (s, t) z^{n} & = \sum_{n} \sum_{k} \sum_{\begin{array}{c} j \\ j = n - k \end{array}} A_{k} (r, t) A_{j} (s, t) z^{n} \\ = \sum_{k} \sum_{\begin{array}{c} j \\ j = n - k \end{array}} A_{k} (r, t) A_{j} (s, t) z^{j + k} \\ = \sum_{k} A_{k} (r, t) z^{k} \sum_{j} A_{j} (s, t) z^{j} \\ = x^{r} x^{s} \\ = x^{r + s} \\ = \sum_{n} A_{n} (r + s, t) z^{n} = x^{r + s} . \end{array}

Equating coeﬃcients yields

\sum_{k} A_{k} (r, t) A_{n - k} (s, t) = A_{n} (r + s, t)

as we needed to show. □

We may also prove Eq. (26) from the preceding two exercises.

Proposition. $\sum_{k \geq 0} (\binom{r - t k}{k}) (\binom{s - t (n - k)}{n - k}) \frac{r}{r - t k} = (\binom{r + s - t n}{n})$ .

Proof. Let $n$ be an arbitrary integer. We must show that

\sum_{k \geq 0} (\binom{r - t k}{k}) (\binom{s - t (n - k)}{n - k}) \frac{r}{r - t k} = (\binom{r + s - t n}{n}) .

From exercise 25, we have that $\sum_{k \geq 0} A_{k} (r, t) z^{k} = x^{r}$ and from exercise 26, we have that $\sum_{j} (\binom{s - t j}{j}) z^{j} = \frac{x^{s + 1}}{(t + 1) x - t}$ . Multiplying both equations yields

\begin{array}{l} x^{r} \frac{x^{s + 1}}{(t + 1) x - t} & = \frac{x^{r + s + 1}}{(t + 1) x - t} \\ = \sum_{k \geq 0} A_{k} (r, t) z^{k} \sum_{j} (\binom{s - t j}{j}) z^{j} \\ = \sum_{k \geq 0} A_{k} (r, t) z^{k} \sum_{\begin{array}{c} n \\ j = n - k \end{array}} (\binom{s - t (n - k)}{n - k}) z^{n - k} \\ = \sum_{n} \sum_{k \geq 0} A_{k} (r, t) (\binom{s - t (n - k)}{n - k}) z^{n} \\ = \sum_{n} \sum_{k \geq 0} (\binom{r - k t}{k}) \frac{r}{r - k t} (\binom{s - t (n - k)}{n - k}) z^{n}; \\ = \sum_{n} \sum_{k \geq 0} (\binom{r - k t}{k}) (\binom{s - t (n - k)}{n - k}) \frac{r}{r - k t} z^{n}; \end{array}

and again, from exercise 26,

\frac{x^{r + s + 1}}{(t + 1) x - t} = \sum_{n} (\binom{r + s - t n}{n}) z^{n},

which gives us the equality

\sum_{n} \sum_{k \geq 0} (\binom{r - k t}{k}) (\binom{s - t (n - k)}{n - k}) \frac{r}{r - k t} z^{n} = \sum_{n} (\binom{r + s - t n}{n}) z^{n} .

Finally, equating coeﬃcients yields

\sum_{k \geq 0} (\binom{r - k t}{k}) (\binom{s - t (n - k)}{n - k}) \frac{r}{r - k t} = (\binom{r + s - t n}{n}),

and hence the result. □

Proposition. $\sum_{k} (\binom{r + t k}{k}) (\binom{s - t k}{n - k}) = \sum_{k \geq 0} (\binom{r + s - k}{n - k}) t^{k}$ for $n$ a nonnegative integer.

Proof. Let $n$ be an arbitrary nonnegative integer. We must show that

\sum_{k} (\binom{r + t k}{k}) (\binom{s - t k}{n - k}) = \sum_{k \geq 0} (\binom{r + s - k}{n - k}) t^{k} .

If $n = 0$ ,

\begin{array}{l} \sum_{k} (\binom{r + t k}{k}) (\binom{s - t k}{n - k}) & = \sum_{k} (\binom{r + t k}{k}) (\binom{s - t k}{- k}) \\ = 0 \\ = \sum_{k \geq 0} (\binom{r + s - k}{- k}) \\ = \sum_{k \geq 0} (\binom{r + s - k}{- k}) t^{k} . \end{array}

Then, assuming

\sum_{k} (\binom{r + t k}{k}) (\binom{s - t k}{n - k}) = \sum_{k \geq 0} (\binom{r + s - k}{n - k}) t^{k}

we must show that

\sum_{k} (\binom{r + t k}{k}) (\binom{s - t k}{n + 1 - k}) = \sum_{k \geq 0} (\binom{r + s - k}{n + 1 - k}) t^{k} .

But from Eq. (26),

\begin{array}{l} \sum_{k} (\binom{r + t k}{k}) (\binom{s - t k}{n + 1 - k}) & = \sum_{k} (\binom{r + t k}{k}) (\binom{s - t k}{n + 1 - k}) \frac{r + t k}{r + t k} \\ \begin{aligned} = \sum_{k} (\binom{r + t k}{k}) (\binom{s - t k}{n + 1 - k}) \frac{r}{r + t k} \\ + \sum_{k} (\binom{r + t k}{k}) (\binom{s - t k}{n + 1 - k}) \frac{t k}{r + t k} \end{aligned} \\ \begin{aligned} = \sum_{k} (\binom{r - (- t) k}{k}) (\binom{(s - t n) - (- t) (n - k)}{n + 1 - k}) \frac{r}{r - (- t) k} \\ + \sum_{k} (\binom{r + t k}{k}) (\binom{s - t k}{n + 1 - k}) \frac{t k}{r + t k} \end{aligned} \\ \begin{aligned} = (\binom{r + (s - t n) - (- t) n}{n + 1}) \\ + \sum_{k} (\binom{r + t k}{k}) (\binom{s - t k}{n + 1 - k}) \frac{t k}{r + t k} \end{aligned} \\ = (\binom{r + s}{n + 1}) + t \sum_{k} \frac{k}{r + t k} (\binom{r + t k}{k}) (\binom{s - t k}{n + 1 - k}) \\ = (\binom{r + s}{n + 1}) + t \sum_{k} (\binom{r + t k - 1}{k - 1}) (\binom{s - t k}{n + 1 - k}) \\ = (\binom{r + s}{n + 1}) + t \sum_{k} (\binom{r + t (k + 1) - 1}{k + 1 - 1}) (\binom{s - t (k + 1)}{n + 1 - (k + 1)}) \\ = (\binom{r + s}{n + 1}) + t \sum_{k} (\binom{r + t - 1 + t k}{k}) (\binom{s - t - t k}{)}) \\ = (\binom{r + s}{n + 1}) + t \sum_{k \geq 0} (\binom{r + t - 1 + s - t - k}{n - k}) t^{k} \\ = (\binom{r + s}{n + 1}) + t \sum_{k \geq 0} (\binom{r + s - k - 1}{n - k}) t^{k} \\ = (\binom{r + s}{n + 1}) + \sum_{k \geq 0} (\binom{r + s - (k + 1)}{n + 1 - (k + 1)}) t^{k + 1} \\ = (\binom{r + s - 0}{n + 1 - 0}) t^{0} + \sum_{k \geq 1} (\binom{r + s - k}{n + 1 - k}) t^{k} \\ = \sum_{k \geq 0} (\binom{r + s - k}{n + 1 - k}) t^{k} \end{array}

as we needed to show. □

Eq. (34) for $r \geq 0$ is

\sum_{k} (\binom{r}{k}) {(- 1)}^{r - k} \sum_{0 \leq j \leq r} b_{j} k^{j} = r! b_{r},

while the general identity proved in exercise 1.2.3-33 is

\sum_{1 \leq k \leq r} \frac{k^{j}}{\prod_{\begin{array}{c} 1 \leq i \leq r \\ i \neq k \end{array}} (k - i)} = \{\begin{matrix} 0 & if 0 \leq j < r - 1 \\ 1 & if j = r - 1 \\ \sum_{1 \leq k \leq r} k & if j = r . \end{matrix}

Thus,

\begin{array}{l} \sum_{k} (\binom{r}{k}) {(- 1)}^{r - k} \sum_{0 \leq j \leq r} b_{j} k^{j} & = \sum_{0 \leq k \leq r} (\binom{r}{k}) {(- 1)}^{r - k} \sum_{0 \leq j \leq r} b_{j} k^{j} \\ = \sum_{0 \leq j \leq r} b_{j} \sum_{0 \leq k \leq r} (\binom{r}{k}) {(- 1)}^{r - k} k^{j} \\ = \sum_{0 \leq j \leq r} b_{j} \sum_{0 \leq k \leq r} \frac{r!}{k! (r - k)!} {(- 1)}^{r - k} k^{j} \\ = r! \sum_{0 \leq j \leq r} b_{j} \sum_{0 \leq k \leq r} \frac{k^{j}}{{(- 1)}^{r - k} k! (r - k)!} \\ = r! \sum_{0 \leq j \leq r} b_{j} \sum_{0 \leq k \leq r} \frac{k^{j}}{\prod_{1 \leq i \leq r - k} (- 1) \prod_{1 \leq i \leq k} i \prod_{1 \leq i \leq r - k} i} \\ = r! \sum_{0 \leq j \leq r} b_{j} \sum_{0 \leq k \leq r} \frac{k^{j}}{\prod_{1 \leq i \leq k} i \prod_{1 \leq i \leq r - k} (- i)} \\ = r! \sum_{0 \leq j \leq r} b_{j} \sum_{0 \leq k \leq r} \frac{k^{j}}{\prod_{0 \leq i \leq k - 1} (k - i) \prod_{k + 1 \leq i \leq r} (k - i)} \\ = r! \sum_{0 \leq j \leq r} b_{j} \sum_{0 \leq k \leq r} \frac{k^{j}}{\prod_{\begin{array}{c} 0 \leq i \leq r \\ i \neq k \end{array}} (k - i)} \\ = r! \sum_{- 1 \leq j \leq r - 1} b_{j + 1} \sum_{1 \leq k \leq r} \frac{k^{j}}{\prod_{\begin{array}{c} 1 \leq i \leq r \\ i \neq k \end{array}} (k - i)} \\ = r! b_{r - 1 + 1} (1) \\ = r! b_{r} \end{array}

and hence the result.

We wish to evaluate the sum from Example 3

\sum_{k} (\binom{n + k}{m + 2 k}) (\binom{2 k}{k}) \frac{{(- 1)}^{k}}{k + 1}

for positive integers $m$ and $n$ , using Eq. (26)

\sum_{k \geq 0} (\binom{1 + 2 k}{k}) (\binom{- m - 1 - 2 k}{n - m - k}) \frac{1}{1 + 2 k} = (\binom{- m}{n - m}) .

But

\begin{array}{l} \sum_{k} (\binom{n + k}{m + 2 k}) (\binom{2 k}{k}) \frac{{(- 1)}^{k}}{k + 1} \\ = \sum_{k} (\binom{n + k}{m + 2 k}) (\binom{2 k}{k}) \frac{{(- 1)}^{k}}{k + 1} \frac{2 k + 1}{2 k + 1} \\ = \sum_{k} (\binom{n + k}{m + 2 k}) \frac{2 k + 1}{k + 1} (\binom{2 k}{k}) \frac{{(- 1)}^{k}}{2 k + 1} \\ = \sum_{k \geq 0} (\binom{n + k}{m + 2 k}) (\binom{2 k + 1}{k + 1}) \frac{{(- 1)}^{k}}{2 k + 1} & from Eq. (7) \\ = \sum_{k \geq 0} (\binom{n + k}{m + 2 k}) (\binom{2 k + 1}{k}) \frac{{(- 1)}^{k}}{2 k + 1} & from Eq. (6) \\ = \sum_{k \geq 0} {(- 1)}^{n + k - m - 2 k} (\binom{- (m + 2 k + 1)}{n + k - m - 2 k}) (\binom{2 k + 1}{k}) \frac{{(- 1)}^{k}}{2 k + 1} & from Eq. (19) \\ = \sum_{k \geq 0} (\binom{- m - 2 k - 1}{n - m - k}) (\binom{2 k + 1}{k}) \frac{{(- 1)}^{n - m - k} {(- 1)}^{k}}{2 k + 1} \\ = \sum_{k \geq 0} (\binom{- m - 2 k - 1}{n - m - k}) (\binom{2 k + 1}{k}) \frac{{(- 1)}^{n - m}}{2 k + 1} \\ = \sum_{k \geq 0} (\binom{- m - 2 k - 1}{n - m - k}) (\binom{2 k + 1}{k}) \frac{{(- 1)}^{n - m}}{2 k + 1} \\ = \sum_{k \geq 0} (\binom{1 + 2 k}{k}) (\binom{- m - 1 - 2 k}{n - m - k}) \frac{{(- 1)}^{n - m}}{1 + 2 k} \\ = {(- 1)}^{n - m} (\binom{- m}{n - m}) & from Eq. (26) \\ = {(- 1)}^{n - m} (\binom{n - m - n + 1 - 1}{n - m}) \\ = (\binom{n - 1}{n - m}) & from Eq. (17) \\ = (\binom{n - 1}{n - 1 - n + m}) & from Eq. (6) \\ = (\binom{n - 1}{m - 1}) \end{array}

and hence the result.

We have

\begin{array}{l} \sum_{k} (\binom{m - r + s}{k}) (\binom{n + r - s}{n - k}) (\binom{r + k}{m + n}) \\ = \sum_{k} (\binom{m - r + s}{k}) (\binom{n + r - s}{n - k}) \sum_{j} (\binom{r}{m + n - j}) (\binom{k}{j}) \\ = \sum_{j} \sum_{k} (\binom{m - r + s}{k}) (\binom{k}{j}) (\binom{n + r - s}{n - k}) (\binom{r}{m + n - j}) \\ = \sum_{j} \sum_{k} (\binom{m - r + s}{j}) (\binom{m - r + s - j}{k - j}) (\binom{n + r - s}{n - k}) (\binom{r}{m + n - j}) & from Eq. (20) \\ = \sum_{j} \sum_{k} (\binom{m - r + s}{j}) (\binom{m - r + s - j}{m - r + s - k}) (\binom{n + r - s}{n - k}) (\binom{r}{m + n - j}) & from Eq. (6) \\ = \sum_{j} \sum_{k} (\binom{m - r + s}{j}) (\binom{m - r + s - j}{m - r + s - k}) (\binom{n + r - s}{r - s + k}) (\binom{r}{m + n - j}) & from Eq. (6) \\ = \sum_{j} (\binom{m - r + s}{j}) (\binom{r}{m + n - j}) \sum_{k} (\binom{m - r + s - j}{m - (k + r - s)}) (\binom{n + r - s}{k + r - s}) \\ = \sum_{j} (\binom{m - r + s}{j}) (\binom{r}{m + n - j}) \sum_{k} (\binom{n + r - s}{k}) (\binom{m - r + s - j}{m - k}) \\ = \sum_{j} (\binom{m - r + s}{j}) (\binom{r}{m + n - j}) (\binom{n + m - j}{m}) & from Eq. (21) \\ = \sum_{j} (\binom{m - r + s}{j}) (\binom{r}{m}) (\binom{r - m}{n - j}) & from Eq. (20) \\ = (\binom{r}{m}) \sum_{j} (\binom{m - r + s}{j}) (\binom{r - m}{n - j}) \\ = (\binom{r}{m}) (\binom{s}{n}) . & from Eq. (21) \end{array}

______________________________________________________________________________________________________________________________

J. F. Plaﬀ, Nova Acta Acad. Scient. Petr. 11 (1797), 38–57.

Proposition. $\sum_{k} [\binom{n}{k}] x^{k} = x^{\bar{n}}$ .

Proof. Let $x^{\bar{n}}$ be the rising factorial power deﬁned as

x^{\bar{n}} = \prod_{0 \leq k \leq n - 1} (x + k) .

We must show that

\sum_{k} [\binom{n}{k}] x^{k} = x^{\bar{n}} .

But

\begin{array}{l} \sum_{k} [\binom{n}{k}] x^{k} & = \sum_{k} [\binom{n}{k}] {(- 1)}^{k} {(- x)}^{k} \\ = \sum_{k} [\binom{n}{k}] {(- 1)}^{- k} {(- x)}^{k} \\ = \sum_{k} [\binom{n}{k}] {(- 1)}^{n - n} {(- 1)}^{- k} {(- x)}^{k} \\ = \sum_{k} [\binom{n}{k}] {(- 1)}^{n} {(- 1)}^{n} {(- 1)}^{- k} {(- x)}^{k} \\ = {(- 1)}^{n} \sum_{k} [\binom{n}{k}] {(- 1)}^{n - k} {(- x)}^{k} \\ = {(- 1)}^{n} {(- x)}^{\underset{̲}{n}} & from Eq. (44) \\ = x^{\bar{n}} & from Eq. 1.2.5-(20) \end{array}

as we needed to show. □

We may prove the formula for factorial falling.

Proposition. ${(x + y)}^{\underset{̲}{n}} = \sum_{k} (\binom{n}{k}) x^{\underset{̲}{k}} y^{\underset{̲}{n - k}}$ .

Proof. Let $n$ be an arbitrary nonnegative integer. We must show that

{(x + y)}^{\underset{̲}{n}} = \sum_{k} (\binom{n}{k}) x^{\underset{̲}{k}} y^{\underset{̲}{n - k}} .

If $n = 0$ ,

\begin{array}{l} {(x + y)}^{\underset{̲}{0}} & = 1 \\ = (\binom{0}{0}) x^{\underset{̲}{0}} y^{\underset{̲}{0}} \\ = \sum_{k} (\binom{0}{k}) x^{\underset{̲}{k}} y^{\underset{̲}{0 - k}} . \end{array}

Then, assuming

{(x + y)}^{\underset{̲}{n}} = \sum_{k} (\binom{n}{k}) x^{\underset{̲}{k}} y^{\underset{̲}{n - k}}

we must show that

{(x + y)}^{\underset{̲}{n + 1}} = \sum_{k} (\binom{n + 1}{k}) x^{\underset{̲}{k}} y^{\underset{̲}{n + 1 - k}} .

But

\begin{array}{l} {(x + y)}^{\underset{̲}{n + 1}} & = (x + y - n) {(x + y)}^{\underset{̲}{n}} \\ = (x + y - n) \sum_{k} (\binom{n}{k}) x^{\underset{̲}{k}} y^{\underset{̲}{n - k}} \\ = \sum_{k} (\binom{n}{k}) x^{\underset{̲}{k}} y^{\underset{̲}{n - k}} ((x - k) + (y - (n - k))) \\ = \sum_{k} (\binom{n}{k}) x^{\underset{̲}{k + 1}} y^{\underset{̲}{n - k}} + \sum_{k} (\binom{n}{k}) x^{\underset{̲}{k}} y^{\underset{̲}{n + 1 - k}} \\ = \sum_{k} (\binom{n}{k - 1}) x^{\underset{̲}{k}} y^{\underset{̲}{n + 1 - k}} + \sum_{k} (\binom{n}{k}) x^{\underset{̲}{k}} y^{\underset{̲}{n + 1 - k}} \\ = \sum_{k} ((\binom{n}{k - 1}) + (\binom{n}{k})) x^{\underset{̲}{k}} y^{\underset{̲}{n + 1 - k}} \\ = \sum_{k} (\binom{n + 1}{k}) x^{\underset{̲}{k}} y^{\underset{̲}{n + 1 - k}} & from Eq. (9) \end{array}

as we needed to show. □

We may also prove the formula for factorial rising.

Proposition. ${(x + y)}^{\bar{n}} = \sum_{k} (\binom{n}{k}) x^{\bar{k}} y^{\bar{n - k}}$ .

Proof. Let $n$ be an arbitrary nonnegative integer. We must show that

{(x + y)}^{\bar{n}} = \sum_{k} (\binom{n}{k}) x^{\bar{k}} y^{\bar{n - k}} .

If $n = 0$ ,

\begin{array}{l} {(x + y)}^{\bar{0}} & = 1 \\ = (\binom{0}{0}) x^{\bar{0}} y^{\bar{0}} \\ = \sum_{k} (\binom{0}{k}) x^{\bar{k}} y^{\bar{0 - k}} . \end{array}

Then, assuming

{(x + y)}^{\bar{n}} = \sum_{k} (\binom{n}{k}) x^{\bar{k}} y^{\bar{n - k}}

we must show that

{(x + y)}^{\bar{n + 1}} = \sum_{k} (\binom{n + 1}{k}) x^{\bar{k}} y^{\bar{n + 1 - k}} .

But

\begin{array}{l} {(x + y)}^{\bar{n + 1}} & = (x + y + n) {(x + y)}^{\bar{n}} \\ = (x + y + n) \sum_{k} (\binom{n}{k}) x^{\bar{k}} y^{\bar{n - k}} \\ = \sum_{k} (\binom{n}{k}) x^{\bar{k}} y^{\bar{n - k}} ((x + k) + (y + (n - k))) \\ = \sum_{k} (\binom{n}{k}) x^{\bar{k + 1}} y^{\bar{n - k}} + \sum_{k} (\binom{n}{k}) x^{\bar{k}} y^{\bar{n + 1 - k}} \\ = \sum_{k} (\binom{n}{k - 1}) x^{\bar{k}} y^{\bar{n + 1 - k}} + \sum_{k} (\binom{n}{k}) x^{\bar{k}} y^{\bar{n + 1 - k}} \\ = \sum_{k} ((\binom{n}{k - 1}) + (\binom{n}{k})) x^{\bar{k}} y^{\bar{n + 1 - k}} \\ = \sum_{k} (\binom{n + 1}{k}) x^{\bar{k}} y^{\bar{n + 1 - k}} & from Eq. (9) \end{array}

as we needed to show. □

Proposition. ${(x + y)}^{\bar{n}} = \sum_{k} (\binom{n}{k}) x {(x - k z + 1)}^{\bar{k - 1}} {(y + k z)}^{\bar{n - k}}$ .

Proof. Let $n$ be an arbitrary nonnegative integer and $x$ an arbitrary nonzero real number. We must show that

{(x + y)}^{\bar{n}} = \sum_{k} (\binom{n}{k}) x {(x - k z + 1)}^{\bar{k - 1}} {(y + k z)}^{\bar{n - k}} .

Given the general identity for arbitrary $a$

\begin{array}{l} a^{\bar{n}} & = \frac{Γ (a + n)}{Γ (a)} \\ = \frac{(a + n)! a}{(a + n) a!} \\ = \frac{(a + n - 1)!}{(a - 1)!} \\ = \frac{(a + n - 1)!}{(a + n - 1 - n)!} \\ = \frac{n! (a + n - 1)!}{n! (a + n - 1 - n)!} \\ = \frac{n! (a + n - 1)!}{n! (a + n - 1 - n)!} \\ = n! (\binom{a + n - 1}{n}), \end{array}

we have that

\begin{array}{l} {(x + y)}^{\bar{n}} \\ = n! (\binom{x + y + n - 1}{n}) \\ = n! \sum_{k} (\binom{x - (z - 1) k}{k}) (\binom{y + n z - 1 - (z - 1) (n - k)}{n - k}) \frac{x}{x - (z - 1) k} & from Eq. (26) \\ = n! \sum_{k} \frac{x}{k} \frac{k}{x - (z - 1) k} (\binom{x - (z - 1) k}{k}) (\binom{y + n z - 1 - (z - 1) (n - k)}{n - k}) \\ = n! \sum_{k} \frac{x}{k} (\binom{x - (z - 1) k - 1}{k - 1}) (\binom{y + n z - 1 - (z - 1) (n - k)}{n - k}) & from Eq. (7) \\ = n! \sum_{k} \frac{x}{k} (\binom{x - (z - 1) k - 1}{k - 1}) (\binom{y + k z + n - k - 1}{n - k}) \\ = \sum_{k} \frac{n!}{k! (n - k)!} (k - 1)! (n - k)! x (\binom{x - k (z - 1) - 1}{k - 1}) (\binom{y + k z + n - k - 1}{n - k}) \\ = \sum_{k} (\binom{n}{k}) x (k - 1)! (\binom{x - k z + 1 + k - 1 - 1}{k - 1}) (n - k)! (\binom{y + k z + n - k - 1}{n - k}) \\ = \sum_{k} (\binom{n}{k}) x {(x - k z + 1)}^{\bar{k - 1}} {(y + k z)}^{\bar{n - k}} \end{array}

as we needed to show. □

______________________________________________________________________________________________________________________________

A. Vandermonde, Mém. Acad. Roy. Sci. (Paris, 1772), part 1, 492; C. Kramp, Élémens d’Arithmétique Universelle (Cologne: 1808), 359; G. Torelli, Giornale di Mat. Battaglini 33 (1895), 179–182; H. A. Rothe, Formulæde Serierum Reversione (Leipzig: 1793), 18.

We may prove the addition formula for Stirling numbers of the ﬁrst kind.

Proposition. $[\binom{n + 1}{m}] = n [\binom{n}{m}] + [\binom{n}{m - 1}]$ .

Proof. Let $m$ and $n$ be arbitrary nonnegative integers. We must show that

[\binom{n + 1}{m}] = n [\binom{n}{m}] + [\binom{n}{m - 1}] .

But from Eq. (44),

\begin{array}{l} \sum_{k} {(- 1)}^{n + 1 - k} [\binom{n + 1}{k}] x^{k} & = x^{\underset{̲}{n + 1}} \\ = (x - n) x^{\underset{̲}{n}} \\ = - n x^{\underset{̲}{n}} + x x^{\underset{̲}{n}} \\ = - n \sum_{k} {(- 1)}^{n - k} [\binom{n}{k}] x^{k} + x \sum_{k} {(- 1)}^{n - k} [\binom{n}{k}] x^{k} \\ = - n \sum_{k} {(- 1)}^{n - k} [\binom{n}{k}] x^{k} + x \sum_{k} {(- 1)}^{n - (k - 1)} [\binom{n}{k - 1}] x^{k - 1} \\ = \sum_{k} {(- 1)}^{n + 1 - k} n [\binom{n}{k}] x^{k} + \sum_{k} {(- 1)}^{n + 1 - k} [\binom{n}{k - 1}] x^{k} \\ = \sum_{k} {(- 1)}^{n + 1 - k} (n [\binom{n}{k}] + [\binom{n}{k - 1}]) x^{k} \end{array}

and hence the result equating coeﬃcients. □

We may also prove the addition formula for Stirling numbers of the second kind.

Proposition. $\{\binom{n + 1}{m}\} = m \{\binom{n}{m}\} + \{\binom{n}{m - 1}\}$ .

Proof. Let $m$ and $n$ be arbitrary nonnegative integers. We must show that

\{\binom{n + 1}{m}\} = m \{\binom{n}{m}\} + \{\binom{n}{m - 1}\} .

But from Eq. (45),

\begin{array}{l} \sum_{k} \{\binom{n + 1}{k}\} x^{\underset{̲}{k}} & = x^{n + 1} \\ = x x^{n} \\ = x \sum_{k} \{\binom{n}{k}\} x^{\underset{̲}{k}} \\ = \sum_{k} \{\binom{n}{k}\} x x^{\underset{̲}{k}} \\ = \sum_{k} \{\binom{n}{k}\} (x x^{\underset{̲}{k}} + k x^{\underset{̲}{k}} - k x^{\underset{̲}{k}}) \\ = \sum_{k} \{\binom{n}{k}\} ((x - k) x^{\underset{̲}{k}} + k x^{\underset{̲}{k}}) \\ = \sum_{k} \{\binom{n}{k}\} (x^{\underset{̲}{k + 1}} + k x^{\underset{̲}{k}}) \\ = \sum_{k} \{\binom{n}{k}\} k x^{\underset{̲}{k}} + \sum_{k} \{\binom{n}{k}\} x^{\underset{̲}{k + 1}} \\ = \sum_{k} k \{\binom{n}{k}\} x^{\underset{̲}{k}} + \sum_{k} \{\binom{n}{k - 1}\} x^{\underset{̲}{k}} \\ = \sum_{k} (k \{\binom{n}{k}\} + \{\binom{n}{k - 1}\}) x^{\underset{̲}{k}} \end{array}

and hence the result equating coeﬃcients. □

Assuming $n$ a nonnegative integer, from Eq. (13),

\begin{array}{l} \sum_{k} (\binom{n}{k}) & = \sum_{k} (\binom{n}{k}) 1^{k} 1^{n - k} \\ = {(1 + 1)}^{n} \\ = 2^{n}, \end{array}

and

\begin{array}{l} \sum_{k} (\binom{n}{k}) {(- 1)}^{k} & = \sum_{k} (\binom{n}{k}) {(- 1)}^{k} 1^{n - k} \\ = {(- 1 + 1)}^{n} \\ = 0^{n} \\ = δ_{n 0} . \end{array}

Again assuming $n$ a nonnegative integer, from the preceding exercise,

\begin{array}{l} \sum_{k even} (\binom{n}{k}) & = \sum_{k} (\binom{n}{k}) - \sum_{k odd} (\binom{n}{k}) \\ = \frac{\sum_{k} (\binom{n}{k}) + \sum_{k even} (\binom{n}{k}) - \sum_{k odd} (\binom{n}{k})}{2} \\ = \frac{\sum_{k} (\binom{n}{k}) + \sum_{k even} (\binom{n}{k}) {(- 1)}^{k} + \sum_{k odd} (\binom{n}{k}) {(- 1)}^{k}}{2} \\ = \frac{\sum_{k} (\binom{n}{k}) + \sum_{k} (\binom{n}{k}) {(- 1)}^{k}}{2} \\ = \frac{2^{n} + δ_{n 0}}{2} \\ = \{\begin{matrix} 1 & if n = 0 \\ 2^{n - 1} & if n > 0 . \end{matrix} \end{array}

Proposition. $\sum_{j \geq 0} (\binom{n}{j m + k}) = \frac{1}{m} \sum_{0 \leq j < m} {(2 \cos \frac{j π}{m})}^{n} \cos \frac{j (n - 2 k) π}{m}$ .

Proof. Let $k$ and $m$ be arbitrary integers such that $0 \leq k < m$ . We must show that

\sum_{j \geq 0} (\binom{n}{j m + k}) = \frac{1}{m} \sum_{0 \leq j < m} {(2 \cos \frac{j π}{m})}^{n} \cos \frac{j (n - 2 k) π}{m} .

Given $ω = e^{2 π i ∕ m}$ and the sum of the geometric progression for $t$ restricted such that $t mod m = k$ ,

\begin{array}{l} \sum_{0 \leq j < m} ω^{j (t - k)} & = \sum_{0 \leq j < m} {(ω^{t - k})}^{j} \\ = \sum_{0 \leq j < m} {(e^{2 π i (t - k) ∕ m})}^{j} \\ = \sum_{0 \leq j < m} {({(- 1)}^{2 (t - k) ∕ m})}^{j} \\ = \sum_{0 \leq j < m} {(1^{(t - k) ∕ m})}^{j} \\ = [t - k \equiv 0 (\mod m)] \sum_{0 \leq j < m} 1^{j} \\ = [t - k \equiv 0 (\mod m)] m \end{array}

we have for the real part that

\begin{array}{l} \sum_{j \geq 0} (\binom{n}{j m + k}) & = \sum_{t mod m = k} (\binom{n}{t}) \\ = \sum_{t - k \equiv 0 (mod m)} (\binom{n}{t}) \\ = \sum_{t} (\binom{n}{t}) [t - k \equiv 0 (mod m)] \\ = \sum_{t} (\binom{n}{t}) \frac{1}{m} \sum_{0 \leq j < m} ω^{j (t - k)} \\ = \frac{1}{m} \sum_{0 \leq j < m} ω^{- j k} \sum_{t} (\binom{n}{t}) ω^{j t} \\ = \frac{1}{m} \sum_{0 \leq j < m} ω^{- j k} {(1 + ω^{j})}^{n} \\ = \frac{1}{m} \sum_{0 \leq j < m} ω^{- j k} {(ω^{j} + 1)}^{n} \\ = \frac{1}{m} \sum_{0 \leq j < m} ω^{- j k} {(ω^{j ∕ 2} ω^{j ∕ 2} + ω^{j ∕ 2} ω^{- j ∕ 2})}^{n} \\ = \frac{1}{m} \sum_{0 \leq j < m} ω^{- j k} ω^{j n ∕ 2} {(ω^{j ∕ 2} + ω^{- j ∕ 2})}^{n} \\ = \frac{1}{m} \sum_{0 \leq j < m} ω^{j (n ∕ 2 - k)} {(ω^{j ∕ 2} + ω^{- j ∕ 2})}^{n} \\ = \frac{1}{m} \sum_{0 \leq j < m} e^{2 π i j (n ∕ 2 - k) ∕ m} {(e^{2 π i j ∕ m 2} + e^{- 2 π i j ∕ m 2})}^{n} \\ = \frac{1}{m} \sum_{0 \leq j < m} e^{i \frac{j (n - 2 k) π}{m}} {(e^{i \frac{j π}{m}} + e^{- i \frac{j π}{m}})}^{n} \\ = \frac{1}{m} \sum_{0 \leq j < m} \cos \frac{j (n - 2 k) π}{m} {(2 \cos \frac{j π}{m})}^{n} \\ = \frac{1}{m} \sum_{0 \leq j < m} {(2 \cos \frac{j π}{m})}^{n} \cos \frac{j (n - 2 k) π}{m} \end{array}

as we needed to show. □

______________________________________________________________________________________________________________________________

C. Ramus, Crelle 11 (1834), 353–355; CMath, exercises 5.75 and 6.57.

Assuming $n$ a nonnegative integer, from exercise 32 we have that

\begin{array}{l} \sum_{k} [\binom{n}{k}] & = \sum_{k} [\binom{n}{k}] 1^{k} \\ = 1^{\bar{n}} \\ = \prod_{0 \leq j \leq n - 1} (1 + j) & from Eq. 1.2.5-(19) \\ = \prod_{1 \leq j \leq n} j \\ = n! \end{array}

and from Eq. (44) we have that

\begin{array}{l} \sum_{k} [\binom{n}{k}] {(- 1)}^{k} & = \sum_{k} [\binom{n}{k}] {(- 1)}^{- k} \\ = \sum_{k} [\binom{n}{k}] {(- 1)}^{n - k - n} \\ = \sum_{k} {(- 1)}^{n - k} [\binom{n}{k}] {(- 1)}^{- n} \\ = \sum_{k} {(- 1)}^{n - k} [\binom{n}{k}] {(- 1)}^{n} \\ = \sum_{k} {(- 1)}^{n - k} [\binom{n}{k}] 1^{k} {(- 1)}^{n} \\ = 1^{\underset{̲}{n}} {(- 1)}^{n} \\ = \prod_{0 \leq j \leq n - 1} (1 - j) {(- 1)}^{n} & from Eq. 1.2.5-(18) \\ = \{\begin{matrix} 1 & if n = 0 \\ - 1 & if n = 1 \\ 0 & otherwise \end{matrix} \\ = δ_{n 0} - δ_{n 1} . \end{array}

Let $x$ and $y$ be arbitrary positive real numbers and deﬁne the beta function $B (x, y)$ as

B (x, y) = \int_{0}^{1} t^{x - 1} {(1 - t)}^{y - 1} d t .

a)

We may show the ﬁrst identity.

Proposition. $B (x, 1) = B (1, x) = 1 ∕ x$ .

Proof. We must show that

B (x, 1) = B (1, x) = 1 ∕ x .

(68)

But by deﬁnition, both

\begin{array}{l} B (x, 1) & = \int_{0}^{1} t^{x - 1} {(1 - t)}^{1 - 1} d t \\ = - \int_{1}^{0} {(1 - t)}^{x - 1} {(1 - (1 - t))}^{1 - 1} d t \\ = \int_{0}^{1} t^{1 - 1} {(1 - t)}^{x - 1} d t \\ = B (1, x) \end{array}

and

\begin{array}{l} B (x, 1) & = \int_{0}^{1} t^{x - 1} {(1 - t)}^{1 - 1} d t \\ = \int_{0}^{1} t^{x - 1} d t \\ = {\frac{t^{x}}{x}|}_{0}^{1} \\ = \frac{1}{x} - \frac{0}{x} \\ = \frac{1}{x} \end{array}

and hence the result. □

b)

We may show the second identity.

Proposition. $B (x + 1, y) + B (x, y + 1) = B (x, y)$ .

Proof. We must show that

B (x + 1, y) + B (x, y + 1) = B (x, y) .

(71)

But

\begin{array}{l} B (x + 1, y) + B (x, y + 1) & = \int_{0}^{1} t^{x + 1 - 1} {(1 - t)}^{y - 1} d t + \int_{0}^{1} t^{x - 1} {(1 - t)}^{y + 1 - 1} d t \\ = \int_{0}^{1} (t^{x + 1 - 1} {(1 - t)}^{y - 1} + t^{x - 1} {(1 - t)}^{y + 1 - 1}) d t \\ = \int_{0}^{1} (t t^{x - 1} {(1 - t)}^{y - 1} + (1 - t) t^{x - 1} {(1 - t)}^{y - 1}) d t \\ = \int_{0}^{1} (t + 1 - t) t^{x - 1} {(1 - t)}^{y - 1} d t \\ = \int_{0}^{1} t^{x - 1} {(1 - t)}^{y - 1} d t \\ = B (x, y) \end{array}

and hence the result. □

c)

We may show the third identity.

Proposition. $B (x, y) = ((x + y) ∕ y) B (x, y + 1)$ .

Proof. We must show that

B (x, y) = ((x + y) ∕ y) B (x, y + 1) .

(73)

But from integration by parts

- \int_{0}^{1} t^{x} y {(1 - t)}^{y - 1} d t = {t^{x} {(1 - t)}^{y}|}_{0}^{1} - \int_{0}^{1} x t^{x - 1} {(1 - t)}^{y} d t

which gives us that

\begin{array}{l} B (x + 1, y) & = \int_{0}^{1} t^{x} {(1 - t)}^{y - 1} d t \\ = - {\frac{t^{x} {(1 - t)}^{y}}{y}|}_{0}^{1} + \frac{x}{y} \int_{0}^{1} t^{x - 1} {(1 - t)}^{y} d t \\ = - {\frac{t^{x} {(1 - t)}^{y}}{y}|}_{0}^{1} + \frac{x}{y} B (x, y + 1) \\ = - \frac{1^{x} {(1 - 1)}^{y}}{y} + \frac{0^{x} {(1 - 0)}^{y}}{y} + \frac{x}{y} B (x, y + 1) \\ = \frac{x}{y} B (x, y + 1) . \end{array}

Then, from (b)

\begin{array}{l} B (x, y) & = B (x + 1, y) + B (x, y + 1) \\ = \frac{x}{y} B (x, y + 1) + B (x, y + 1) \\ = \frac{x + y}{y} B (x, y + 1) \end{array}

and hence the result. □

Deﬁne the gamma function for positive integers $m$ as

Γ_{m} (x) = \frac{m^{x} m!}{\prod_{0 \leq j \leq m} (x + j)},

so that from exercise 1.2.5-19

Γ_{m} (x) = m^{x} B (x, m + 1) .

a)

We may prove the ﬁrst identity.

Proposition. $B (x, y) = \frac{Γ_{m} (y) m^{x}}{Γ_{m} (x + y)} B (x, y + m + 1)$ .

Proof. Let $m$ be a positive integer. We must show that

B (x, y) = \frac{Γ_{m} (y) m^{x}}{Γ_{m} (x + y)} B (x, y + m + 1) .

As an initial corollary, we will ﬁrst show for positive integers $k$ that

B (x, y) = \prod_{0 \leq j < k} \frac{x + y + j}{y + j} B (x, y + k) .

If $k = 1$ we have from exercise 40 (c) that

\begin{array}{l} B (x, y) & = \frac{x + y}{y} B (x, y + 1) \\ = \prod_{0 \leq j < k} \frac{x + y + j}{y + j} B (x, y + k) . \end{array}

Then, assuming

B (x, y) = \prod_{0 \leq j < k} \frac{x + y + j}{y + j} B (x, y + k)

we must show that

B (x, y) = \prod_{0 \leq j < k + 1} \frac{x + y + j}{y + j} B (x, y + k + 1) .

But again from exercise 40 (c)

\begin{array}{l} B (x, y) & = \prod_{0 \leq j < k} \frac{x + y + j}{y + j} B (x, y + k) \\ = \prod_{0 \leq j < k} \frac{x + y + j}{y + j} \frac{x + y + k}{y + k} B (x, y + k + 1) \\ = \prod_{0 \leq j < k + 1} \frac{x + y + j}{y + j} B (x, y + k + 1) \end{array}

and hence the interim result. Then ﬁnally,

\begin{array}{l} B (x, y) & = \prod_{0 \leq j < m + 1} \frac{x + y + j}{y + j} B (x, y + m + 1) \\ = \prod_{0 \leq j \leq m} \frac{x + y + j}{y + j} B (x, y + m + 1) \\ = \frac{\prod_{0 \leq j \leq m} (x + y + j)}{\prod_{0 \leq j \leq m} (y + j)} B (x, y + m + 1) \\ = \frac{m^{x + y} m! \prod_{0 \leq j \leq m} (x + y + j)}{m^{x + y} m! \prod_{0 \leq j \leq m} (y + j)} B (x, y + m + 1) \\ = (\frac{m^{y} m!}{\prod_{0 \leq j \leq m} (y + j)} / \frac{m^{x + y} m!}{\prod_{0 \leq j \leq m} (x + y + j)}) m^{x} B (x, y + m + 1) \\ = \frac{Γ_{m} (y) m^{x}}{Γ_{m} (x + y)} B (x, y + m + 1) \end{array}

as we needed to show. □

b)

We may show the second identity.

Proposition. $B (x, y) = \frac{Γ (x) Γ (y)}{Γ (x + y)}$ .

Proof. Let $m$ be a positive integer. We must show that

B (x, y) = \frac{Γ (x) Γ (y)}{Γ (x + y)} .

It is suﬃcient to show that

\lim_{m \to \infty} m^{x} B (x, y + m + 1) = Γ (x) .

Note that B is monotonically decreasing for positive $x$ and $y$ . That is, if $(x, y) \leq (x, y + 1)$ , then $B (x, y) \geq B (x, y + 1)$ , since from exercise 40

\begin{array}{l} x > 0 \land y > 0 \\ \Leftrightarrow \frac{x}{y} \geq 0 \\ \Leftrightarrow \frac{x}{y} + 1 \geq 1 \\ \Leftrightarrow \frac{x + y}{y} \geq 1 \\ \Leftrightarrow \frac{x + y}{y} B (x, y + 1) \geq B (x, y + 1) \\ \Leftrightarrow B (x, y) \geq B (x, y + 1) . \end{array}

Then, since B is monotonically decreasing and from exercise 1.2.5-19,

\begin{array}{l} y + m + 1 \leq y + m + 1 < n + m + 2 \\ \Leftrightarrow B (x, y + m + 2) < B (x, y + m + 1) \leq B (x, y + m + 1) \\ \Leftrightarrow \frac{Γ_{y + m + 1} (x)}{{(y + m + 1)}^{x}} < B (x, y + m + 1) \leq \frac{Γ_{y + m} (x)}{{(y + m)}^{x}} \\ \Leftrightarrow \frac{Γ_{y + m + 1} (x)}{m^{x} {(1 + (y + 1) ∕ m)}^{x}} < B (x, y + m + 1) \leq \frac{Γ_{y + m} (x)}{m^{x} {(1 + y ∕ m)}^{x}} \\ \begin{aligned} \Leftrightarrow {(\frac{m}{y + m + 1})}^{x} Γ_{y + m + 1} (x) < m^{x} B (x, y + m + 1) \\ \leq {(\frac{m}{y + m})}^{x} Γ_{y + m} (x) \end{aligned} \\ \begin{aligned} \Leftrightarrow \lim_{m \to \infty} {(\frac{m}{y + m + 1})}^{x} Γ_{y + m + 1} (x) < \lim_{m \to \infty} m^{x} B (x, y + m + 1) \\ \leq \lim_{m \to \infty} {(\frac{m}{y + m})}^{x} Γ_{y + m} (x) \end{aligned} \\ \Leftrightarrow \lim_{m \to \infty} Γ_{y + m + 1} (x) < \lim_{m \to \infty} m^{x} B (x, y + m + 1) \leq \lim_{m \to \infty} Γ_{y + m} (x) \\ \Leftrightarrow \lim_{m \to \infty} Γ_{m} (x) < \lim_{m \to \infty} m^{x} B (x, y + m + 1) \leq \lim_{m \to \infty} Γ_{m} (x) \\ \Leftrightarrow Γ (x) < \lim_{m \to \infty} m^{x} B (x, y + m + 1) \leq Γ (x) \\ \Leftrightarrow \lim_{m \to \infty} m^{x} B (x, y + m + 1) = Γ (x) . \end{array}

And so from (a),

\begin{array}{l} B (x, y) & = \lim_{m \to \infty} \frac{Γ_{m} (y) m^{x}}{Γ_{m} (x + y)} B (x, y + m + 1) \\ = \lim_{m \to \infty} \frac{m^{x} B (x, y + m + 1) Γ_{m} (y)}{Γ_{m} (x + y)} \\ = \frac{Γ (x) Γ (y)}{Γ (x + y)} \end{array}

as we needed to show. □

From exercise 41 (b) we have

\begin{array}{l} (\binom{r}{k}) & = \frac{r!}{k! (r - k)!} \\ = \frac{(r + 2)! (k + 1) (r - k + 1)}{(r + 1) (r + 2) (k + 1)! (r - k + 1)!} \\ = \frac{Γ (r + 2)}{(r + 1) Γ (k + 1) Γ (r - k + 1)} \\ = \frac{Γ (k + 1 + r - k + 1)}{(r + 1) Γ (k + 1) Γ (r - k + 1)} \\ = \frac{1}{(r + 1) B (k + 1, r - k + 1)} . \end{array}

______________________________________________________________________________________________________________________________

L. Ramshaw, Inf. Proc. Letters 6 (1977), 223–226.

Proposition. $B (1 ∕ 2, 1 ∕ 2) = π$ .

Proof. Deﬁne the beta function $B (x, y)$ as

B (x, y) = \int_{0}^{1} t^{x - 1} {(1 - t)}^{y - 1} d t .

We must show that

B (1 ∕ 2, 1 ∕ 2) = π .

But for $u = t^{1 ∕ 2}$ , $d u = \frac{1}{2 t^{1 ∕ 2}} d t$ ,

\begin{array}{l} B (1 ∕ 2, 1 ∕ 2) & = \int_{0}^{1} t^{1 ∕ 2 - 1} {(1 - t)}^{1 ∕ 2 - 1} d t \\ = \int_{0}^{1} \frac{1}{t^{1 ∕ 2} {(1 - t)}^{1 ∕ 2}} d t \\ = \int_{0}^{1} \frac{2 t^{1 ∕ 2}}{t^{1 ∕ 2} {(1 - u^{2})}^{1 ∕ 2}} d u \\ = 2 \int_{0}^{1} \frac{1}{{(1 - u^{2})}^{1 ∕ 2}} d u \\ = 2 {\arcsin u|}_{0}^{1} \\ = 2 (π ∕ 2 - 0) \\ = π \end{array}

as we needed to show. □

Proposition. $(\binom{r}{1 ∕ 2}) = 2^{2 r + 1} / (\binom{2 r}{r}) π$ .

Proof. As a corollary, we will prove Gauss’s multiplication formula. That is, that

Γ (n z) = {(2 π)}^{(1 - n) ∕ 2} n^{n z - 1 ∕ 2} \prod_{0 \leq k \leq n - 1} Γ (z + \frac{k}{n}) .

By Stirling’s formula as $m \to \infty$ , we have

\begin{array}{l} Γ (z + \frac{k}{n}) & = (z + \frac{k}{n} - 1) Γ (z + \frac{k}{n} - 1) \\ = \lim_{m \to \infty} m^{z + k ∕ n - 1} m! / \prod_{0 \leq j \leq m - 1} (z + \frac{k}{n} + j) \\ = \lim_{m \to \infty} m^{z + k ∕ n - 1} \sqrt{2 π m} {(\frac{m}{e})}^{m} / \prod_{0 \leq j \leq m - 1} (z + \frac{k}{n} + j) \\ = \lim_{m \to \infty} m^{z + k ∕ n - 1 ∕ 2} \sqrt{2 π} {(\frac{m n}{e})}^{m} / \prod_{0 \leq j \leq m - 1} (n z + k + j n), \end{array}

and

\begin{array}{l} \prod_{0 \leq k \leq n - 1} Γ (z + \frac{k}{n}) \\ = \lim_{m \to \infty} m^{n z - n ∕ 2} m^{\sum_{0 \leq k \leq n - 1} k ∕ n} {(\sqrt{2 π})}^{n} {(\frac{m n}{e})}^{m n} / \prod_{0 \leq k \leq n - 1} \prod_{0 \leq j \leq m - 1} (n z + k + j n) \\ = \lim_{m \to \infty} m^{n z - n ∕ 2} m^{\sum_{0 \leq k \leq n - 1} k ∕ n} {(\sqrt{2 π})}^{n} {(\frac{m n}{e})}^{m n} / \prod_{0 \leq j \leq m n - 1} (n z + j) \\ = \lim_{m \to \infty} m^{n z - 1 ∕ 2} {(\sqrt{2 π})}^{n} {(\frac{m n}{e})}^{m n} / \prod_{0 \leq j \leq m n - 1} (n z + j) \\ = \lim_{m \to \infty} {(m ∕ n)}^{n z - 1 ∕ 2} {(\sqrt{2 π})}^{n} {(\frac{(m ∕ n) n}{e})}^{(m ∕ n) n} / \prod_{0 \leq j \leq (m ∕ n) n - 1} (n z + j) \\ = \lim_{m \to \infty} m^{n z - 1 ∕ 2} n^{1 ∕ 2 - n z} {(\sqrt{2 π})}^{n} {(\frac{m}{e})}^{m} / \prod_{0 \leq j \leq m - 1} (n z + j) \\ = \lim_{m \to \infty} m^{n z - 1} n^{1 ∕ 2 - n z} {(\sqrt{2 π})}^{n - 1} \sqrt{2 π m} {(\frac{m}{e})}^{m} / \prod_{0 \leq j \leq m - 1} (n z + j) \\ = \lim_{m \to \infty} m^{n z - 1} n^{1 ∕ 2 - n z} {(\sqrt{2 π})}^{n - 1} m! / \prod_{0 \leq j \leq m - 1} (n z + j) \\ = {(2 π)}^{(n - 1) ∕ 2} n^{1 ∕ 2 - n z} \lim_{m \to \infty} m^{n z - 1} m! / \prod_{0 \leq j \leq m - 1} (n z + j) \\ = {(2 π)}^{(n - 1) ∕ 2} n^{1 ∕ 2 - n z} (n z - 1) Γ (n z - 1) \\ = {(2 π)}^{(n - 1) ∕ 2} n^{1 ∕ 2 - n z} Γ (n z), \end{array}

and hence the result

Γ (n z) = {(2 π)}^{(1 - n) ∕ 2} n^{n z - 1 ∕ 2} \prod_{0 \leq k \leq n - 1} Γ (z + \frac{k}{n}) .

For the proof, we must show that

(\binom{r}{1 ∕ 2}) = 2^{2 r + 1} / (\binom{2 r}{r}) π .

But from exercise 42 and since $Γ (3 ∕ 2) = Γ (1 ∕ 2) ∕ 2 = \sqrt{π} ∕ 2$ ,

\begin{array}{l} (\binom{r}{1 ∕ 2}) & = \frac{1}{(r + 1) B (1 ∕ 2 + 1, r - 1 ∕ 2 + 1)} \\ = \frac{1}{(r + 1) B (3 ∕ 2, r + 1 ∕ 2)} \\ = \frac{Γ (3 ∕ 2 + r + 1 ∕ 2)}{(r + 1) Γ (3 ∕ 2) Γ (r + 1 ∕ 2)} \\ = \frac{Γ (r + 2)}{(r + 1) Γ (3 ∕ 2) Γ (r + 1 ∕ 2)} \\ = \frac{2 Γ (r + 2)}{(r + 1) \sqrt{π} Γ (r + 1 ∕ 2)} \end{array}

and

\begin{array}{l} (\binom{2 r}{r}) & = \frac{1}{(2 r + 1) B (r + 1, 2 r - r + 1)} \\ = \frac{1}{(2 r + 1) B (r + 1, r + 1)} \\ = \frac{Γ (r + 1 + r + 1)}{(2 r + 1) Γ (r + 1) Γ (r + 1)} \\ = \frac{Γ (2 r + 2)}{(2 r + 1) Γ (r + 1) Γ (r + 1)} . \end{array}

Multiplying both equalities yields

\begin{array}{l} (\binom{r}{1 ∕ 2}) (\binom{2 r}{r}) & = \frac{2 Γ (r + 2)}{(r + 1) \sqrt{π} Γ (r + 1 ∕ 2)} \frac{Γ (2 r + 2)}{(2 r + 1) Γ (r + 1) Γ (r + 1)} \\ = \frac{2 Γ (r + 2) Γ (2 r + 2)}{(r + 1) \sqrt{π} Γ (r + 1 ∕ 2) (2 r + 1) Γ (r + 1) Γ (r + 1)} \\ = \frac{2 Γ (r + 2) (2 r + 1) Γ (2 r + 1)}{(r + 1) \sqrt{π} Γ (r + 1 ∕ 2) (2 r + 1) Γ (r + 1) Γ (r + 1)} \\ = \frac{2 Γ (r + 2) Γ (2 r + 1)}{(r + 1) \sqrt{π} Γ (r + 1 ∕ 2) Γ (r + 1) Γ (r + 1)} \\ = \frac{2 (r + 1) Γ (r + 1) Γ (2 r + 1)}{(r + 1) \sqrt{π} Γ (r + 1 ∕ 2) Γ (r + 1) Γ (r + 1)} \\ = \frac{2 Γ (2 r + 1)}{\sqrt{π} Γ (r + 1 ∕ 2) Γ (r + 1)} \end{array}

if and only if

(\binom{r}{1 ∕ 2}) = 2 Γ (2 r + 1) / \sqrt{π} Γ (r + 1 ∕ 2) Γ (r + 1) (\binom{2 r}{r}) .

That is, it is suﬃcient to show that

\frac{Γ (2 r + 1)}{Γ (r + 1) Γ (r + 1 ∕ 2)} = \frac{2^{2 r}}{\sqrt{π}} .

But, by Guass’s multiplication formula,

\begin{array}{l} \frac{Γ (2 r + 1)}{Γ (r + 1) Γ (r + 1 ∕ 2)} \\ = \frac{2 r}{Γ (r + 1) Γ (r + 1 ∕ 2)} Γ (2 r) \\ = \frac{2 r}{Γ (r + 1) Γ (r + 1 ∕ 2)} {(2 π)}^{(1 - 2) ∕ 2} 2^{2 r - 1 ∕ 2} \prod_{0 \leq k \leq 2 - 1} Γ (r + \frac{k}{2}) \\ = \frac{2 r}{Γ (r + 1) Γ (r + 1 ∕ 2)} {(2 π)}^{- 1 ∕ 2} 2^{2 r - 1 ∕ 2} Γ (r) Γ (r + \frac{1}{2}) \\ = \frac{2^{2 r} r Γ (r) Γ (r + 1 ∕ 2)}{\sqrt{π} Γ (r + 1) Γ (r + 1 ∕ 2)} \\ = \frac{2^{2 r} r Γ (r)}{\sqrt{π} r Γ (r)} \\ = \frac{2^{2 r}}{\sqrt{π}} . \end{array}

And so,

\begin{array}{l} (\binom{r}{1 ∕ 2}) & = 2 Γ (2 r + 1) / \sqrt{π} Γ (r + 1 ∕ 2) Γ (r + 1) (\binom{2 r}{r}) \\ = \frac{Γ (2 r + 1)}{Γ (r + 1) Γ (r + 1 ∕ 2)} 2 / \sqrt{π} (\binom{2 r}{r}) \\ = \frac{2^{2 r}}{\sqrt{π}} 2 / \sqrt{π} (\binom{2 r}{r}) \\ = 2^{2 r} 2 / \sqrt{π} \sqrt{π} (\binom{2 r}{r}) \\ = 2^{2 r + 1} / (\binom{2 r}{r}) π \end{array}

as we needed to show. □

From exercise 42 and Stirling’s approximation,

\begin{array}{l} \lim_{r \to \infty} (\binom{r}{k}) ∕ r^{k} & = \lim_{r \to \infty} \frac{1}{r^{k} (r + 1) B (k + 1, r - k + 1)} \\ = \lim_{r \to \infty} \frac{Γ (k + 1 + r - k + 1)}{r^{k} (r + 1) Γ (k + 1) Γ (r - k + 1)} \\ = \lim_{r \to \infty} \frac{Γ (r + 2)}{r^{k} (r + 1) Γ (k + 1) Γ (r - k + 1)} \\ = \frac{1}{Γ (k + 1)} \lim_{r \to \infty} \frac{(r + 1) Γ (r + 1)}{r^{k} (r + 1) Γ (r - k + 1)} \\ = \frac{1}{Γ (k + 1)} \lim_{r \to \infty} \frac{Γ (r + 1)}{r^{k} Γ (r - k + 1)} \\ = \frac{1}{Γ (k + 1)} \lim_{r \to \infty} \frac{r!}{r^{k} (r - k)!} \\ = \frac{1}{Γ (k + 1)} \lim_{r \to \infty} \frac{\sqrt{2 π r} {(r ∕ e)}^{r}}{r^{k} \sqrt{2 π (r - k)} {((r - k) ∕ e)}^{r - k}} \\ = \frac{1}{Γ (k + 1)} \lim_{r \to \infty} \sqrt{\frac{r}{r - k}} \frac{1}{e^{r}} \frac{e^{r}}{e^{k}} \frac{{(r - k)}^{k} r^{r}}{r^{k} {(r - k)}^{r}} \\ = \frac{1}{Γ (k + 1)} \lim_{r \to \infty} \sqrt{\frac{r}{r - k}} \frac{1}{e^{k}} \frac{{((r - k) ∕ r)}^{k}}{{((r - k) ∕ r)}^{r}} \\ = \frac{1}{Γ (k + 1)} \lim_{r \to \infty} \sqrt{\frac{r}{r - k}} \frac{1}{e^{k}} \frac{{(1 - k ∕ r)}^{k}}{{(1 - k ∕ r)}^{r}} \\ = \frac{1}{Γ (k + 1)} \frac{1}{e^{k}} \lim_{r \to \infty} \frac{1}{{(1 - k ∕ r)}^{r}} \\ = \frac{1}{Γ (k + 1)} \frac{1}{e^{k}} \frac{1}{e^{- k}} \\ = \frac{1}{Γ (k + 1)} . \end{array}

Assuming that both $x$ and $y$ are large, using Stirling’s approximation, we ﬁnd that

\begin{array}{l} (\binom{x + y}{y}) & = \frac{1}{(x + y + 1) B (x + 1, y + 1)} \\ = \frac{1}{(x + y + 1) B (y + 1, x + y - y + 1)} \\ = \frac{1}{(x + y + 1) B (y + 1, x + 1)} \\ = \frac{Γ (x + y + 2)}{(x + y + 1) Γ (y + 1) Γ (x + 1)} \\ = \frac{(x + y + 1) Γ (x + y + 1)}{(x + y + 1) Γ (x + 1) Γ (y + 1)} \\ = \frac{Γ (x + y + 1)}{Γ (x + 1) Γ (y + 1)} \\ = \frac{Γ (x + y + 1)}{Γ (x + 1) Γ (y + 1)} \\ = \frac{(x + y)!}{x! y!} \\ \approx \frac{\sqrt{2 π (x + y)} {((x + y) ∕ e)}^{x + y}}{\sqrt{2 π x} {(x ∕ e)}^{x} \sqrt{2 π y} {(y ∕ e)}^{y}} \\ = \sqrt{\frac{x + y}{2 π x y}} \frac{{(x + y)}^{x} {(x + y)}^{y} e^{x} e^{y}}{x^{x} y^{y} e^{x + y}} \\ = \sqrt{\frac{1}{2 π} (\frac{1}{x} + \frac{1}{y})} {(1 + \frac{y}{x})}^{x} {(1 + \frac{x}{y})}^{y} . \end{array}

In particular, when $n$ is large,

\begin{array}{l} (\binom{2 n}{n}) & = (\binom{n + n}{n}) \\ \approx \sqrt{\frac{1}{2 π} (\frac{1}{n} + \frac{1}{n})} {(1 + \frac{n}{n})}^{n} {(1 + \frac{n}{n})}^{n} \\ = \sqrt{\frac{1}{2 π} (\frac{2}{n})} {(2)}^{n} {(2)}^{n} \\ = \frac{2^{2 n}}{\sqrt{π n}} \\ = \frac{4^{n}}{\sqrt{π n}} . \end{array}

We may prove the equalities.

Proposition. $(\binom{r}{k}) (\binom{r - 1 ∕ 2}{k}) = (\binom{2 r}{k}) (\binom{2 r - k}{k}) / 4^{k} = (\binom{2 r}{2 k}) (\binom{2 k}{k}) / 4^{k}$ for integer $k$ .

Proof. Let $k$ be an arbitrary integer. We must show that

(\binom{r}{k}) (\binom{r - 1 ∕ 2}{k}) = (\binom{2 r}{k}) (\binom{2 r - k}{k}) / 4^{k} = (\binom{2 r}{2 k}) (\binom{2 k}{k}) / 4^{k} .

In the case that $k < 0$ , we have

\begin{array}{l} (\binom{r}{k}) (\binom{r - 1 ∕ 2}{k}) & = 0 \\ = (\binom{2 r}{k}) (\binom{2 r - k}{k}) / 4^{k}; \end{array}

and in the case that $k = 0$ , we have

\begin{array}{l} (\binom{r}{k}) (\binom{r - 1 ∕ 2}{k}) & = 1 \\ = (\binom{2 r}{k}) (\binom{2 r - k}{k}) / 4^{k} . \end{array}

That is, in the case that $k \leq 0$ , we have

\begin{array}{l} (\binom{r}{k}) (\binom{r - 1 ∕ 2}{k}) & = δ_{k 0} \\ = (\binom{2 r}{k}) (\binom{2 r - k}{k}) / 4^{k} . \end{array}

In the case that $k = r$ , we have

\begin{array}{l} (\binom{r}{k}) (\binom{r - 1 ∕ 2}{k}) & = (\binom{k - 1 ∕ 2}{k}) \\ = \frac{1}{(k - 1 ∕ 2 + 1) B (k + 1, k - 1 ∕ 2 - k + 1)} \\ = \frac{1}{(k + 1 ∕ 2) B (k + 1, 1 ∕ 2)} \\ = \frac{Γ (k + 1 + 1 ∕ 2)}{(k + 1 ∕ 2) Γ (k + 1) Γ (1 ∕ 2)} \\ = \frac{Γ (k + 1 ∕ 2)}{Γ (k + 1) Γ (1 ∕ 2)} \\ = \frac{Γ (1 ∕ 2) Γ (k + 1 ∕ 2)}{Γ {(1 ∕ 2)}^{2} Γ (k + 1)} \\ = \frac{Γ (1 ∕ 2) Γ (k + 1 ∕ 2)}{π Γ (k + 1)} \\ = \frac{2 (k + 1) Γ (3 ∕ 2) Γ (k + 1 ∕ 2)}{π Γ (3 ∕ 2 + k + 1 ∕ 2)} \\ = \frac{2 (k + 1) B (3 ∕ 2, k + 1 ∕ 2)}{π} \\ = 2 / \frac{1}{(k + 1) B (1 ∕ 2 + 1, k - 1 ∕ 2 + 1)} π \\ = 2 / (\binom{k}{1 ∕ 2}) π \\ = 2^{2 k + 1} / (\binom{k}{1 ∕ 2}) π 4^{k} \\ = (\binom{2 k}{k}) / 4^{k} . \end{array}

It remains to consider the case when $0 < k \neq r$ . Assuming

(\binom{r}{k}) (\binom{r - 1 ∕ 2}{k}) = (\binom{2 r}{k}) (\binom{2 r - k}{k}) / 4^{k}

we must show that

(\binom{r}{k + 1}) (\binom{r - 1 ∕ 2}{k + 1}) = (\binom{2 r}{k + 1}) (\binom{2 r - (k + 1)}{k + 1}) / 4^{k + 1} .

As a corollary, note that from Eqs. (7) and (8) with $0 \neq k \neq r$ we have

\begin{array}{l} (\binom{r}{k}) & = \frac{r}{k} (\binom{r - 1}{k - 1}) \\ = \frac{r}{k} \frac{r - k + 1}{r} (\binom{r}{k - 1}) \\ = \frac{r - k + 1}{k} (\binom{r}{k - 1}) . \end{array}

Then

\begin{array}{l} (\binom{r}{k + 1}) (\binom{r - 1 ∕ 2}{k + 1}) \\ = (\binom{r}{k + 1}) (\binom{r - 1 ∕ 2}{k + 1}) \\ = \frac{r - (k + 1) + 1}{k + 1} (\binom{r}{(k + 1) - 1}) \frac{r - 1 ∕ 2 - (k + 1) + 1}{k + 1} (\binom{r - 1 ∕ 2}{(k + 1) - 1}) \\ = \frac{(r - k) (r - k - 1 ∕ 2)}{{(k + 1)}^{2}} (\binom{r}{k}) (\binom{r - 1 ∕ 2}{k}) \\ = \frac{(r - k) (r - k - 1 ∕ 2)}{{(k + 1)}^{2}} (\binom{2 r}{k}) (\binom{2 r - k}{k}) / 4^{k} \\ = \frac{4 (r - k) (r - k - 1 ∕ 2)}{4 {(k + 1)}^{2}} (\binom{2 r}{k}) (\binom{2 r - k}{k}) / 4^{k} \\ = \frac{2 (2 r - k) (r - k - 1 ∕ 2)}{4 {(k + 1)}^{2}} (\binom{2 r}{k}) \frac{2 (r - k)}{2 r - k} (\binom{2 r - k}{k}) / 4^{k} \\ = \frac{2 (2 r - k) (r - k - 1 ∕ 2)}{4 {(k + 1)}^{2}} (\binom{2 r}{k}) (\binom{2 r - k - 1}{k}) / 4^{k} \\ = \frac{1}{4} \frac{2 r - (k + 1) + 1}{k + 1} (\binom{2 r}{(k + 1) - 1}) \frac{(2 r - k - 1) - (k + 1) + 1}{k + 1} (\binom{2 r - k - 1}{(k + 1) - 1}) / 4^{k} \\ = \frac{1}{4} (\binom{2 r}{k + 1}) (\binom{2 r - k - 1}{k + 1}) / 4^{k} \\ = (\binom{2 r}{k + 1}) (\binom{2 r - k - 1}{k + 1}) / 4^{k + 1} \\ = (\binom{2 r}{k + 1}) (\binom{2 r - (k + 1)}{k + 1}) / 4^{k + 1} . \end{array}

That is, for $k$ an arbitrary integer

(\binom{r}{k}) (\binom{r - 1 ∕ 2}{k}) = (\binom{2 r}{k}) (\binom{2 r - k}{k}) / 4^{k} .

And ﬁnally, from Eq. (20)

\begin{array}{l} (\binom{2 r}{k}) (\binom{2 r - k}{k}) / 4^{k} \\ = (\binom{2 r}{k}) (\binom{2 r - k}{2 k - k}) / 4^{k} \\ = (\binom{2 r}{2 k}) (\binom{2 k}{k}) / 4^{k} \end{array}

as we needed to show. □

For the special case $r = - 1 ∕ 2$ , we have the simpler equalities

\begin{array}{l} (\binom{- 1 ∕ 2}{k}) (\binom{- 1 ∕ 2 - 1 ∕ 2}{k}) & = (\binom{- 1 ∕ 2}{k}) (\binom{- 1}{k}) \\ = (\binom{- 2 ∕ 2}{k}) (\binom{- 2 ∕ 2 - k}{k}) / 4^{k} \\ = (\binom{- 1}{k}) (\binom{- 1 - k}{k}) / 4^{k} \\ = (\binom{- 2 ∕ 2}{2 k}) (\binom{2 k}{k}) / 4^{k} \\ = (\binom{- 1}{2 k}) (\binom{2 k}{k}) / 4^{k} \end{array}

if and only if, from Eq. (17)

\begin{array}{l} (\binom{- 1 ∕ 2}{k}) & = \frac{(\binom{- 1}{2 k}) (\binom{2 k}{k})}{4^{k} (\binom{- 1}{k})} \\ = \frac{{(- 1)}^{2 k} (\binom{2 k - (- 1) - 1}{2 k}) (\binom{2 k}{k})}{4^{k} (\binom{- 1}{k})} \\ = \frac{(\binom{2 k}{k})}{4^{k} (\binom{- 1}{k})} \\ = \frac{(\binom{2 k}{k})}{4^{k} {(- 1)}^{k} (\binom{k - (- 1) - 1}{k})} \\ = \frac{(\binom{2 k}{k})}{4^{k} {(- 1)}^{k}} \\ = {(\frac{- 1}{4})}^{k} (\binom{2 k}{k}) . \end{array}

That is, we have the simpler formula

(\binom{- 1 ∕ 2}{k}) = {(\frac{- 1}{4})}^{k} (\binom{2 k}{k}) .

Proposition. $\sum_{k \geq 0} (\binom{n}{k}) \frac{{(- 1)}^{k}}{k + x} = \frac{n!}{\prod_{0 \leq j \leq n} x + j} = \frac{1}{x (\binom{n + x}{n})}$ .

Proof. Let $n$ and $k$ be arbitrary, nonnegative integers. We must show that

\sum_{k \geq 0} (\binom{n}{k}) \frac{{(- 1)}^{k}}{k + x} = \frac{n!}{\prod_{0 \leq j \leq n} x + j} = \frac{1}{x (\binom{n + x}{n})} .

First, note that

\begin{array}{l} \frac{n!}{\prod_{0 \leq j \leq n} x + j} & = \frac{n!}{x^{\bar{n + 1}}} \\ = \frac{n!}{{(x + n + 1 - 1)}^{\underset{̲}{n + 1}}} \\ = \frac{n!}{{(x + n)}^{\underset{̲}{n + 1}}} \\ = \frac{n! (x + n - (n + 1))!}{(x + n)!} \\ = \frac{n! (x - 1)!}{(x + n)!} \\ = \frac{n! x!}{x (n + x)!} \\ = \frac{n! (n + x - n)!}{x (n + x)!} \\ = \frac{1}{x (\binom{n + x}{n})} . \end{array}

Then, if $n = 0$ ,

\begin{array}{l} \sum_{k \geq 0} (\binom{n}{k}) \frac{{(- 1)}^{k}}{k + x} & = (\binom{0}{0}) \frac{{(- 1)}^{0}}{0 + x} \\ = \frac{1}{x} \\ = \frac{1}{x (\binom{0 + x}{0})} . \end{array}

Assuming

\sum_{k \geq 0} (\binom{n}{k}) \frac{{(- 1)}^{k}}{k + x} = \frac{n!}{\prod_{0 \leq j \leq n} x + j} = \frac{1}{x (\binom{n + x}{n})}

we must show that

\sum_{k \geq 0} (\binom{n + 1}{k}) \frac{{(- 1)}^{k}}{k + x} = \frac{(n + 1)!}{\prod_{0 \leq j \leq n + 1} x + j} = \frac{1}{x (\binom{n + 1 + x}{n + 1})} .

But

\begin{array}{l} \sum_{k \geq 0} (\binom{n + 1}{k}) \frac{{(- 1)}^{k}}{x + k} \\ = \sum_{0 \leq k \leq n + 1} (\binom{n + 1}{k}) \frac{{(- 1)}^{k}}{x + k} \\ = (\binom{n + 1}{n + 1}) \frac{{(- 1)}^{n + 1}}{x + n + 1} + \sum_{0 \leq k \leq n} (\binom{n + 1}{k}) \frac{{(- 1)}^{k}}{x + k} \\ = \frac{{(- 1)}^{n + 1}}{x + n + 1} + \sum_{0 \leq k \leq n} (\binom{n + 1}{k}) \frac{{(- 1)}^{k}}{x + k} \\ = \frac{{(- 1)}^{n + 1}}{x + n + 1} + \sum_{0 \leq k \leq n} ((\binom{n}{k}) + (\binom{n}{k - 1})) \frac{{(- 1)}^{k}}{x + k} \\ = \frac{{(- 1)}^{n + 1}}{x + n + 1} + \sum_{0 \leq k \leq n} (\binom{n}{k}) \frac{{(- 1)}^{k}}{x + k} + \sum_{0 \leq k \leq n} (\binom{n}{k - 1}) \frac{{(- 1)}^{k}}{x + k} \\ = \frac{{(- 1)}^{n + 1}}{x + n + 1} + \sum_{0 \leq k \leq n} (\binom{n}{k}) \frac{{(- 1)}^{k}}{x + k} + \sum_{- 1 \leq k \leq n - 1} (\binom{n}{k}) \frac{{(- 1)}^{k + 1}}{x + k + 1} \\ = \frac{{(- 1)}^{n + 1}}{x + n + 1} + \sum_{0 \leq k \leq n} (\binom{n}{k}) \frac{{(- 1)}^{k}}{x + k} - \sum_{- 1 \leq k \leq n - 1} (\binom{n}{k}) \frac{{(- 1)}^{k}}{(x + 1) + k} \\ = \frac{{(- 1)}^{n + 1}}{x + n + 1} - (\binom{n}{- 1}) \frac{- 1}{x} + (\binom{n}{n}) \frac{{(- 1)}^{n}}{x + n + 1} + \sum_{0 \leq k \leq n} (\binom{n}{k}) \frac{{(- 1)}^{k}}{x + k} - \sum_{0 \leq k \leq n} (\binom{n}{k}) \frac{{(- 1)}^{k}}{(x + 1) + k} \\ = \frac{{(- 1)}^{n + 1} + {(- 1)}^{n}}{x + n + 1} - (\binom{n}{- 1}) \frac{- 1}{x} + \sum_{0 \leq k \leq n} (\binom{n}{k}) \frac{{(- 1)}^{k}}{x + k} - \sum_{0 \leq k \leq n} (\binom{n}{k}) \frac{{(- 1)}^{k}}{(x + 1) + k} \\ = \sum_{0 \leq k \leq n} (\binom{n}{k}) \frac{{(- 1)}^{k}}{x + k} - \sum_{0 \leq k \leq n} (\binom{n}{k}) \frac{{(- 1)}^{k}}{(x + 1) + k} \\ = \frac{1}{x (\binom{n + x}{n})} - \frac{1}{(x + 1) (\binom{n + (x + 1)}{n})} \\ = \frac{n! x!}{x (n + x)!} - \frac{n! (x + 1)!}{(x + 1) (n + x + 1)!} \\ = \frac{n! x! (x + 1) (n + x + 1)}{x (x + 1) (n + x)! (n + x + 1)} - \frac{n! x (x + 1)!}{x (x + 1) (n + x + 1)!} \\ = \frac{n! (x - 1)! (n + x + 1)}{(n + x + 1)!} - \frac{n! x!}{(n + x + 1)!} \\ = \frac{n! (x - 1)! (n + x + 1) - n! x!}{(n + x + 1)!} \\ = \frac{n! (x - 1)! (n + x + 1) - n! (x - 1)! x}{(n + x + 1)!} \\ = \frac{n! (x - 1)! (n + 1)}{(n + x + 1)!} \\ = \frac{(n + 1)! (x - 1)!}{(n + x + 1)!} \\ = \frac{(n + 1)! ((n + 1 + x) - (n + 1))!}{x (n + 1 + x)!} \\ = \frac{1}{x (\binom{n + 1 + x}{n + 1})} \end{array}

as we needed to show. □

Given

{(1 + x)}^{r} = {(1 - x^{2})}^{r} {(1 - x)}^{- r}

and the binomial theorem, we have that

\begin{array}{l} \sum_{0 \leq m} (\binom{r}{m}) x^{m} & = {(1 + x)}^{r} \\ = {(1 - x^{2})}^{r} {(1 - x)}^{- r} \\ = (\sum_{0 \leq k \leq r} (\binom{r}{k}) {(- 1)}^{k} x^{2 k}) (\sum_{0 \leq l} (\binom{- r}{l}) {(- 1)}^{l} x^{l}) \\ = \sum_{0 \leq k \leq r} \sum_{0 \leq l} (\binom{r}{k}) (\binom{- r}{l}) {(- 1)}^{k + l} x^{2 k + l} \\ = \sum_{0 \leq k \leq r} \sum_{0 \leq m - 2 k} (\binom{r}{k}) (\binom{- r}{m - 2 k}) {(- 1)}^{k + m - 2 k} x^{m} \\ = \sum_{0 \leq k \leq r} \sum_{2 k \leq m} (\binom{r}{k}) (\binom{- r}{m - 2 k}) {(- 1)}^{m - k} x^{m} \\ = \sum_{0 \leq k \leq r} \sum_{2 k \leq m} (\binom{r}{k}) (\binom{- r}{m - 2 k}) {(- 1)}^{m + k} x^{m} \\ = \sum_{0 \leq k \leq r} ((\sum_{2 k \leq m} (\binom{r}{k}) (\binom{- r}{m - 2 k}) {(- 1)}^{m + k} x^{m}) + 0) \\ = \sum_{0 \leq k \leq r} ((\sum_{2 k \leq m} (\binom{r}{k}) (\binom{- r}{m - 2 k}) {(- 1)}^{m + k} x^{m}) + (\sum_{0 \leq m < 2 k} (\binom{r}{k}) (\binom{- r}{m - 2 k}) {(- 1)}^{m + k} x^{m})) \\ = \sum_{0 \leq k \leq r} \sum_{0 \leq m} (\binom{r}{k}) (\binom{- r}{m - 2 k}) {(- 1)}^{m + k} x^{m} \\ = \sum_{0 \leq m} \sum_{0 \leq k \leq r} (\binom{r}{k}) (\binom{- r}{m - 2 k}) {(- 1)}^{m + k} x^{m} \end{array}

which implies the relation

(\binom{r}{m}) = \sum_{0 \leq k \leq r} (\binom{r}{k}) (\binom{- r}{m - 2 k}) {(- 1)}^{m + k}

for integer $m$ .

Proposition. ${(x + y)}^{n} = \sum_{0 \leq k \leq n} (\binom{n}{k}) x {(x - k z)}^{k - 1} {(y + k z)}^{n - k}$ for integer $n \geq 0$ , $x \neq 0$ , $x + y = 0$ .

Proof. Let $n$ be an arbitrary nonnegative integer and $x$ , $y$ , $z$ arbitrary reals such that $x \neq 0$ , $x + y = 0$ . We must show that

{(x + y)}^{n} = \sum_{0 \leq k \leq n} (\binom{n}{k}) x {(x - k z)}^{k - 1} {(y + k z)}^{n - k};

or equivalently, since $x + y = 0$ , that

δ_{n, 0} = \sum_{0 \leq k \leq n} (\binom{n}{k}) x {(x - k z)}^{k - 1} {(- x + k z)}^{n - k} .

But by the binomial theorem and Eq. (34)

\begin{array}{l} \sum_{0 \leq k \leq n} (\binom{n}{k}) x {(x - k z)}^{k - 1} {(- x + k z)}^{n - k} \\ = \sum_{0 \leq k \leq n} (\binom{n}{k}) x {(x - k z)}^{k - 1} {(- 1)}^{n - k} {(x - k z)}^{n - k} \\ = \sum_{0 \leq k \leq n} (\binom{n}{k}) {(- 1)}^{n - k} {(x - k z)}^{k - 1 + n - k} x \\ = \sum_{0 \leq k \leq n} (\binom{n}{k}) {(- 1)}^{n - k} {(x - k z)}^{n - 1} x \\ = \sum_{0 \leq k \leq n} (\binom{n}{k}) {(- 1)}^{n - k} x {(x - z k)}^{n - 1} \\ = \sum_{0 \leq k \leq n} (\binom{n}{k}) {(- 1)}^{n - k} x \sum_{0 \leq m \leq n - 1} (\binom{n - 1}{m}) x^{n - 1 - m} {(- z k)}^{m} \\ = \sum_{0 \leq k \leq n} (\binom{n}{k}) {(- 1)}^{n - k} \sum_{0 \leq m \leq n - 1} (\binom{n - 1}{m}) x^{n - m} {(- 1)}^{m} z^{m} k^{m} \\ = n! (\binom{n - 1}{n}) x^{n - n} {(- 1)}^{n} z^{n} \\ = δ_{n, 0} \end{array}

as we needed to show. □

Proposition. ${(x + y)}^{n} = \sum_{0 \leq k} (\binom{n}{k}) x {(x - k z)}^{k - 1} {(y + k z)}^{n - k}$ for integer $n \geq 0$ , $x \neq 0$ , $x + y = 0$ .

Proof. Let $n$ be an arbitrary nonnegative integer and $x$ , $y$ , $z$ arbitrary reals such that $x \neq 0$ , $x + y = 0$ . We must show that

\sum_{0 \leq k} (\binom{n}{k}) x {(x - k z)}^{k - 1} {(y + k z)}^{n - k} = {(x + y)}^{n};

or equivalently, since $x + y = x + y \Rightarrow y = (x + y) - x$ , that

\sum_{0 \leq k} (\binom{n}{k}) x {(x - k z)}^{k - 1} {((x + y) - x + k z)}^{n - k} = {(x + y)}^{n} .

But from Eq. (6), the binomial theorem, Eq. (20), and exercise 50

\begin{array}{l} \sum_{0 \leq k} (\binom{n}{k}) x {(x - k z)}^{k - 1} {((x + y) - x + k z)}^{n - k} \\ = \sum_{0 \leq k} (\binom{n}{n - k}) x {(x - k z)}^{k - 1} {((x + y) - x + k z)}^{n - k} \\ = \sum_{0 \leq k} (\binom{n}{n - k}) x {(x - k z)}^{k - 1} {((x + y) + (- x + k z))}^{n - k} \\ = \sum_{0 \leq k} (\binom{n}{n - k}) x {(x - k z)}^{k - 1} \sum_{0 \leq m} (\binom{n - k}{m}) {(x + y)}^{m} {(- x + k z)}^{n - k - m} \\ = \sum_{0 \leq k} \sum_{0 \leq m} (\binom{n}{n - k}) (\binom{n - k}{m}) {(x + y)}^{m} x {(x - k z)}^{k - 1} {(- x + k z)}^{n - k - m} \\ = \sum_{0 \leq k} \sum_{0 \leq m} (\binom{n}{m}) (\binom{n - m}{n - m - k}) {(x + y)}^{m} x {(x - k z)}^{k - 1} {(- x + k z)}^{n - k - m} \\ = \sum_{0 \leq m} (\binom{n}{m}) {(x + y)}^{m} \sum_{0 \leq k} (\binom{n - m}{n - m - k}) x {(x - k z)}^{k - 1} {(- x + k z)}^{n - k - m} \\ = \sum_{0 \leq m} (\binom{n}{m}) {(x + y)}^{m} δ_{n - m, 0} \\ = (\binom{n}{n}) {(x + y)}^{n} \\ = {(x + y)}^{n} \end{array}

as we needed to show. □

______________________________________________________________________________________________________________________________

A. Hurwitz, Acta Mathematica 26 (1902), 199–203.

We may prove that Abel’s binomial formula

{(x + y)}^{n} = \sum_{0 \leq k} (\binom{n}{k}) x {(x - k z)}^{k - 1} {(y + k z)}^{n - k}

is not always valid when $n < 0$ by evaluating the particular case when $n = x = - 1$ , $y = z = 1$ ; and

\begin{array}{l} \sum_{0 \leq k} (\binom{n}{k}) x {(x - k z)}^{k - 1} {(y + k z)}^{n - k} \\ = \sum_{0 \leq k} (\binom{- 1}{k}) (- 1) {((- 1) - k)}^{k - 1} {(1 + k)}^{- 1 - k} \\ = \sum_{0 \leq k} (\binom{- 1}{k}) {(- 1)}^{k} {(k + 1)}^{k - 1} {(k + 1)}^{- k - 1} \\ = \sum_{0 \leq k} (\binom{- 1}{k}) {(- 1)}^{k} {(k + 1)}^{- 2} \\ = \sum_{0 \leq k} {(k + 1)}^{- 2} & from Eq. (17) \\ = \sum_{1 \leq k} k^{- 2} \end{array}

where $\sum_{1 \leq k} k^{- 2}$ is the Riemann zeta function $ζ (- 2) = π^{2} ∕ 6 \neq 0 = {(- 1 + 1)}^{- 1} = {(x + y)}^{n}$ .

a)

We may prove the identity by induction.

Proposition. $\sum_{k = 0}^{m} (\binom{r}{k}) (\binom{s}{n - k}) (n r - (r + s) k) = (m + 1) (n - m) (\binom{r}{m + 1}) (\binom{s}{n - m})$ for integers $m$ , $n$ .

Proof. Let $m$ and $n$ be arbitrary integers such that $m$ is nonnegative. We must show that

\sum_{k = 0}^{m} (\binom{r}{k}) (\binom{s}{n - k}) (n r - (r + s) k) = (m + 1) (n - m) (\binom{r}{m + 1}) (\binom{s}{n - m}) .

If $m = 0$

\begin{array}{l} \sum_{k = 0}^{m} (\binom{r}{k}) (\binom{s}{n - k}) (n r - (r + s) k) & = \sum_{k = 0}^{0} (\binom{r}{k}) (\binom{s}{n - k}) (n r - (r + s) k) \\ = (\binom{r}{0}) (\binom{s}{n - 0}) (n r - (r + s) (0)) \\ = (\binom{r}{0}) (\binom{s}{n}) (n r) \\ = (\binom{s}{n}) (n r) \\ = n r (\binom{s}{n}) \\ = n r \frac{1! (r - 1)!}{1! (r - 1)!} (\binom{s}{n}) \\ = n r \frac{(r - 1)!}{1! (r - 1)!} (\binom{s}{n}) \\ = n \frac{r!}{1! (r - 1)!} (\binom{s}{n}) \\ = n (\binom{r}{1}) (\binom{s}{n}) \\ = (1) (n) (\binom{r}{1}) (\binom{s}{n}) \\ = (0 + 1) (n - 0) (\binom{r}{0 + 1}) (\binom{s}{n - 0}) \\ = (m + 1) (n - m) (\binom{r}{m + 1}) (\binom{s}{n - m}) . \end{array}

Then, assuming

\sum_{k = 0}^{m} (\binom{r}{k}) (\binom{s}{n - k}) (n r - (r + s) k) = (m + 1) (n - m) (\binom{r}{m + 1}) (\binom{s}{n - m})

we must show that

\begin{array}{l} \sum_{k = 0}^{m + 1} (\binom{r}{k}) (\binom{s}{n - k}) (n r - (r + s) k) \\ = ((m + 1) + 1) (n - (m + 1)) (\binom{r}{(m + 1) + 1}) (\binom{s}{n - (m + 1)}) . \end{array}

But from the inductive hypothesis as well as Eqs. (7) and (8)

\begin{array}{l} \sum_{k = 0}^{m + 1} (\binom{r}{k}) (\binom{s}{n - k}) (n r - (r + s) k) \\ = \sum_{k = 0}^{m} (\binom{r}{k}) (\binom{s}{n - k}) (n r - (r + s) k) + (\binom{r}{m + 1}) (\binom{s}{n - (m + 1)}) (n r - (r + s) (m + 1)) \\ = (m + 1) (n - m) (\binom{r}{m + 1}) (\binom{s}{n - m}) + (\binom{r}{m + 1}) (\binom{s}{n - (m + 1)}) (n r - (r + s) (m + 1)) \\ \begin{aligned} = (m + 1) (n - m) (\binom{r}{m + 1}) \frac{s}{n - m} (\binom{s - 1}{n - m - 1}) \\ + (\binom{r}{m + 1}) (\binom{s}{n - (m + 1)}) (n r - (r + s) (m + 1)) \end{aligned} \\ = (m + 1) s (\binom{r}{m + 1}) (\binom{s - 1}{n - m - 1}) + (\binom{r}{m + 1}) (\binom{s}{n - (m + 1)}) (n r - (r + s) (m + 1)) \\ \begin{aligned} = (m + 1) s (\binom{r}{m + 1}) \frac{s - (n - m - 1)}{s} (\binom{s}{n - m - 1}) \\ + (\binom{r}{m + 1}) (\binom{s}{n - (m + 1)}) (n r - (r + s) (m + 1)) \end{aligned} \\ \begin{aligned} = (m + 1) (s - n + m + 1) (\binom{r}{m + 1}) (\binom{s}{n - (m + 1)}) \\ + (\binom{r}{m + 1}) (\binom{s}{n - (m + 1)}) (n r - (r + s) (m + 1)) \end{aligned} \\ = ((m + 1) (s - n + m + 1) + (n r - (r + s) (m + 1))) (\binom{r}{m + 1}) (\binom{s}{n - (m + 1)}) \\ = ((m + 1) ((s - n + m + 1) - (r + s)) + n r) (\binom{r}{m + 1}) (\binom{s}{n - (m + 1)}) \\ = ((m + 1) (- r - n + m + 1) + n r) (\binom{r}{m + 1}) (\binom{s}{n - (m + 1)}) \\ = (n r + (- r - n + m + 1) (m + 1)) (\binom{r}{m + 1}) (\binom{s}{n - (m + 1)}) \\ = (n r - r (m + 1) - n (m + 1) + {(m + 1)}^{2}) (\binom{r}{m + 1}) (\binom{s}{n - (m + 1)}) \\ = (n - (m + 1)) (r - (m + 1)) (\binom{r}{m + 1}) (\binom{s}{n - (m + 1)}) \\ = r (n - (m + 1)) \frac{r - (m + 1)}{r} (\binom{r}{m + 1}) (\binom{s}{n - (m + 1)}) \\ = r (n - (m + 1)) (\binom{r - 1}{m + 1}) (\binom{s}{n - (m + 1)}) \\ = ((m + 1) + 1) (n - (m + 1)) \frac{r}{(m + 1) + 1} (\binom{r - 1}{m + 1}) (\binom{s}{n - (m + 1)}) \\ = ((m + 1) + 1) (n - (m + 1)) (\binom{r}{(m + 1) + 1}) (\binom{s}{n - (m + 1)}) \end{array}

as we needed to show. □

b)

We may derive the formula as a special case of the identity in part (a).

Given the relations from exercise 47, since

\begin{array}{l} (\binom{1 ∕ 2}{n}) = \frac{{(- 1)}^{n - 1}}{2^{2 n - 1} (2 n - 1)} (\binom{2 n - 1}{n}) - δ_{n 0} \\ \Leftrightarrow (\binom{2 n - 1}{n}) = ((\binom{1 ∕ 2}{n}) + δ_{n 0}) \frac{2^{2 n - 1} (2 n - 1)}{{(- 1)}^{n - 1}} \end{array}

and

\begin{array}{l} (\binom{- 1 ∕ 2}{n}) = \frac{{(- 1)}^{n}}{2^{2 n}} (\binom{2 n}{n}) \\ \Leftrightarrow (\binom{2 n}{n}) = (\binom{- 1 ∕ 2}{n}) \frac{2^{2 n}}{{(- 1)}^{n}} \end{array}

we have that

\begin{array}{l} \sum_{k = 0}^{m} (\binom{2 k - 1}{k}) (\binom{2 n - 2 k}{n - k}) \frac{- 1}{2 k - 1} \\ = \sum_{k = 0}^{m} ((\binom{1 ∕ 2}{k}) + δ_{k 0}) \frac{2^{2 k - 1} (2 k - 1)}{{(- 1)}^{k - 1}} (\binom{2 n - 2 k}{n - k}) \frac{- 1}{2 k - 1} \\ = \sum_{k = 0}^{m} ((\binom{1 ∕ 2}{k}) + δ_{k 0}) 2^{2 k - 1} {(- 1)}^{k} (\binom{2 n - 2 k}{n - k}) \\ = \sum_{k = 0}^{m} ((\binom{1 ∕ 2}{k}) + δ_{k 0}) 2^{2 k - 1} {(- 1)}^{k} (\binom{2 (n - k)}{n - k}) \\ = \sum_{k = 0}^{m} ((\binom{1 ∕ 2}{k}) + δ_{k 0}) 2^{2 k - 1} {(- 1)}^{k} (\binom{- 1 ∕ 2}{n - k}) \frac{2^{2 (n - k)}}{{(- 1)}^{n - k}} \\ = \sum_{k = 0}^{m} ((\binom{1 ∕ 2}{k}) + δ_{k 0}) 2^{2 n - 1} {(- 1)}^{n} (\binom{- 1 ∕ 2}{n - k}) \\ = {(- 1)}^{n} 2^{2 n - 1} \sum_{k = 0}^{m} ((\binom{1 ∕ 2}{k}) (\binom{- 1 ∕ 2}{n - k}) + δ_{k 0} (\binom{- 1 ∕ 2}{n - k})) \\ = {(- 1)}^{n} 2^{2 n - 1} (\sum_{k = 0}^{m} (\binom{1 ∕ 2}{k}) (\binom{- 1 ∕ 2}{n - k}) + (\binom{- 1 ∕ 2}{n})) . \end{array}

Then, setting $r = \frac{1}{2}$ , $s = - \frac{1}{2}$ in the result of (a) yields

\begin{array}{l} \sum_{k = 0}^{m} (\binom{1 ∕ 2}{k}) (\binom{- 1 ∕ 2}{n - k}) (n ∕ 2 - (1 ∕ 2 - 1 ∕ 2) k) \\ = \sum_{k = 0}^{m} (\binom{1 ∕ 2}{k}) (\binom{- 1 ∕ 2}{n - k}) (n ∕ 2) \\ = (m + 1) (n - m) (\binom{1 ∕ 2}{m + 1}) (\binom{- 1 ∕ 2}{n - m}) \end{array}

so that, again with the relations from exercise 47, as well as Eqs. (7) and (8),

\begin{array}{l} {(- 1)}^{n} 2^{2 n - 1} (\sum_{k = 0}^{m} (\binom{1 ∕ 2}{k}) (\binom{- 1 ∕ 2}{n - k}) + (\binom{- 1 ∕ 2}{n})) \\ = {(- 1)}^{n} 2^{2 n - 1} (\frac{2 (m + 1) (n - m)}{n} (\binom{1 ∕ 2}{m + 1}) (\binom{- 1 ∕ 2}{n - m}) + (\binom{- 1 ∕ 2}{n})) \\ \begin{aligned} = {(- 1)}^{n} 2^{2 n - 1} \frac{2 (m + 1) (n - m)}{n} \frac{{(- 1)}^{m + 1 - 1}}{2^{2 (m + 1)} (2 (m + 1) - 1)} (\binom{2 (m + 1)}{m + 1}) \frac{{(- 1)}^{n - m}}{2^{2 (n - m)}} (\binom{2 (n - m)}{n - m}) \\ + {(- 1)}^{n} 2^{2 n - 1} \frac{{(- 1)}^{n}}{2^{2 n}} (\binom{2 n}{n}) \end{aligned} \\ = \frac{(m + 1) (n - m)}{2^{2} n (2 m + 1)} (\binom{2 m + 2}{m + 1}) (\binom{2 n - 2 m}{n - m}) + \frac{1}{2} (\binom{2 n}{n}) \\ = \frac{(m + 1) (n - m)}{2^{2} n (2 m + 1)} \frac{2 m + 2}{m + 1} (\binom{2 m + 1}{m}) (\binom{2 n - 2 m}{n - m}) + \frac{1}{2} (\binom{2 n}{n}) \\ = \frac{(m + 1) (n - m)}{2 n (2 m + 1)} (\binom{2 m + 1}{m}) (\binom{2 n - 2 m}{n - m}) + \frac{1}{2} (\binom{2 n}{n}) \\ = \frac{(m + 1) (n - m)}{2 n (2 m + 1)} \frac{2 m + 1}{2 m + 1 - m} (\binom{2 m + 1 - 1}{m}) (\binom{2 n - 2 m}{n - m}) + \frac{1}{2} (\binom{2 n}{n}) \\ = \frac{n - m}{2 n} (\binom{2 m}{m}) (\binom{2 n - 2 m}{n - m}) + \frac{1}{2} (\binom{2 n}{n}) . \end{array}

Hence

\sum_{k = 0}^{m} (\binom{2 k - 1}{k}) (\binom{2 n - 2 k}{n - k}) \frac{- 1}{2 k - 1} = \frac{n - m}{2 n} (\binom{2 m}{m}) (\binom{2 n - 2 m}{n - m}) + \frac{1}{2} (\binom{2 n}{n}) .

Let

A_{n + 1} = {[a_{i j}]}_{n + 1} = {[(\binom{i}{j})]}_{n + 1} = {[\begin{matrix} (\binom{0}{0}) & (\binom{0}{1}) & \dots & (\binom{0}{n}) \\ (\binom{1}{0}) & (\binom{1}{1}) & \dots & (\binom{1}{n}) \\ ⋮ & ⋮ & ⋱ & ⋮ \\ (\binom{n}{0}) & (\binom{n}{1}) & \dots & (\binom{n}{n}) \end{matrix}]}_{n + 1}

represent Pascal’s triangle as a matrix. We want to ﬁnd another matrix $B_{n + 1} = {[b_{i j}]}_{n + 1}$ such that

A_{n + 1} B_{n + 1} = B_{n + 1} A_{n + 1} = I_{n + 1} = {[δ_{i j}]}_{n + 1} .

But by the deﬁnition of matrix multiplication

\begin{array}{l} B_{n + 1} A_{n + 1} & = \sum_{0 \leq k \leq n} b_{i k} a_{k j} \\ = \sum_{0 \leq k \leq n} b_{i k} (\binom{k}{j}) \\ = δ_{i j} \\ = \sum_{0 \leq k \leq i} (\binom{i}{k}) (\binom{k}{j}) {(- 1)}^{i - k} & from Eq. (33) \\ = \sum_{0 \leq k \leq n} (\binom{i}{k}) (\binom{k}{j}) {(- 1)}^{i + k} \\ = \sum_{0 \leq k \leq n} {(- 1)}^{i + k} (\binom{i}{k}) (\binom{k}{j}) . \end{array}

Hence, for arbitrary $k$ , $0 \leq k \leq n$

b_{i k} (\binom{k}{j}) = {(- 1)}^{i + k} (\binom{i}{k}) (\binom{k}{j}) \Leftrightarrow b_{i k} = {(- 1)}^{i + k} (\binom{i}{k})

and in particular for $k = j$

b_{i j} = {(- 1)}^{i + j} (\binom{i}{j})

as we wanted to ﬁnd, so that the inverse matrix is given by

B_{n + 1} = {[b_{i j}]}_{n + 1} = {[{(- 1)}^{i + j} (\binom{i}{j})]}_{n + 1} = {[\begin{matrix} (\binom{0}{0}) & - (\binom{0}{1}) & \dots & {(- 1)}^{n} (\binom{0}{n}) \\ - (\binom{1}{0}) & (\binom{1}{1}) & \dots & {(- 1)}^{1 + n} (\binom{1}{n}) \\ ⋮ & ⋮ & ⋱ & ⋮ \\ {(- 1)}^{n} (\binom{n}{0}) & {(- 1)}^{n + 1} (\binom{n}{1}) & \dots & (\binom{n}{n}) \end{matrix}]}_{n + 1} .

Let

A_{n + 1} = {[a_{i j}]}_{n + 1} = {[[\binom{i}{j}]]}_{n + 1} = {[\begin{matrix} [\binom{0}{0}] & [\binom{0}{1}] & \dots & [\binom{0}{n}] \\ [\binom{1}{0}] & [\binom{1}{1}] & \dots & [\binom{1}{n}] \\ ⋮ & ⋮ & ⋱ & ⋮ \\ [\binom{n}{0}] & [\binom{n}{1}] & \dots & [\binom{n}{n}] \end{matrix}]}_{n + 1}

represent Stirling’s triangle of the ﬁrst kind as a matrix. We want to ﬁnd another matrix $B_{n + 1} = {[b_{i j}]}_{n + 1}$ such that

A_{n + 1} B_{n + 1} = B_{n + 1} A_{n + 1} = I_{n + 1} = {[δ_{i j}]}_{n + 1} .

But by the deﬁnition of matrix multiplication

\begin{array}{l} B_{n + 1} A_{n + 1} & = \sum_{0 \leq k \leq n} b_{i k} a_{k j} \\ = \sum_{0 \leq k \leq n} b_{i k} [\binom{k}{j}] \\ = δ_{i j} \\ = δ_{j i} \\ = \sum_{0 \leq k \leq i} \{\binom{i}{k}\} [\binom{k}{j}] {(- 1)}^{i - k} & from Eq. (47) \\ = \sum_{0 \leq k \leq n} {(- 1)}^{i + k} \{\binom{i}{k}\} [\binom{k}{j}] . \end{array}

Hence, for arbitrary $k$ , $0 \leq k \leq n$

b_{i k} [\binom{k}{j}] = {(- 1)}^{i + k} \{\binom{i}{k}\} [\binom{k}{j}] \Leftrightarrow b_{i k} = {(- 1)}^{i + k} \{\binom{i}{k}\}

and in particular for $k = j$

b_{i j} = {(- 1)}^{i + j} \{\binom{i}{j}\}

as we wanted to ﬁnd, so that the inverse matrix is given by

B_{n + 1} = {[b_{i j}]}_{n + 1} = {[{(- 1)}^{i + j} \{\binom{i}{j}\}]}_{n + 1} = {[\begin{matrix} \{\binom{0}{0}\} & - \{\binom{0}{1}\} & \dots & {(- 1)}^{n} \{\binom{0}{n}\} \\ - \{\binom{1}{0}\} & \{\binom{1}{1}\} & \dots & {(- 1)}^{1 + n} \{\binom{1}{n}\} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ {(- 1)}^{n} \{\binom{n}{0}\} & {(- 1)}^{n + 1} \{\binom{n}{1}\} & \dots & \{\binom{n}{n}\} \end{matrix}]}_{n + 1} .

Similarly, let

A_{n + 1}^{'} = {[a_{i j}^{'}]}_{n + 1} = {[\{\binom{i}{j}\}]}_{n + 1} = {[\begin{matrix} \{\binom{0}{0}\} & \{\binom{0}{1}\} & \dots & \{\binom{0}{n}\} \\ \{\binom{1}{0}\} & \{\binom{1}{1}\} & \dots & \{\binom{1}{n}\} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ \{\binom{n}{0}\} & \{\binom{n}{1}\} & \dots & \{\binom{n}{n}\} \end{matrix}]}_{n + 1}

represent Stirling’s triangle of the second kind as a matrix. We want to ﬁnd another matrix $B_{n + 1}^{'} = {[b_{i j}^{'}]}_{n + 1}$ such that

A_{n + 1}^{'} B_{n + 1}^{'} = B_{n + 1}^{'} A_{n + 1}^{'} = I_{n + 1} = {[δ_{i j}]}_{n + 1} .

But by the deﬁnition of matrix multiplication

\begin{array}{l} B_{n + 1}^{'} A_{n + 1}^{'} & = \sum_{0 \leq k \leq n} b_{i k}^{'} a_{k j}^{'} \\ = \sum_{0 \leq k \leq n} b_{i k}^{'} \{\binom{k}{j}\} \\ = δ_{i j} \\ = δ_{j i} \\ = \sum_{0 \leq k \leq i} [\binom{i}{k}] \{\binom{k}{j}\} {(- 1)}^{i - k} & from Eq. (47) \\ = \sum_{0 \leq k \leq n} {(- 1)}^{i + k} [\binom{i}{k}] \{\binom{k}{j}\} . \end{array}

Hence, for arbitrary $k$ , $0 \leq k \leq n$

b_{i k}^{'} \{\binom{k}{j}\} = {(- 1)}^{i + k} [\binom{i}{k}] \{\binom{k}{j}\} \Leftrightarrow b_{i k}^{'} = {(- 1)}^{i + k} [\binom{i}{k}]

and in particular for $k = j$

b_{i j}^{'} = {(- 1)}^{i + j} [\binom{i}{j}]

as we wanted to ﬁnd, so that the inverse matrix is given by

B_{n + 1}^{'} = {[b_{i j}^{'}]}_{n + 1} = {[{(- 1)}^{i + j} [\binom{i}{j}]]}_{n + 1} = {[\begin{matrix} [\binom{0}{0}] & - [\binom{0}{1}] & \dots & {(- 1)}^{n} [\binom{0}{n}] \\ - [\binom{1}{0}] & [\binom{1}{1}] & \dots & {(- 1)}^{1 + n} [\binom{1}{n}] \\ ⋮ & ⋮ & ⋱ & ⋮ \\ {(- 1)}^{n} [\binom{n}{0}] & {(- 1)}^{n + 1} [\binom{n}{1}] & \dots & [\binom{n}{n}] \end{matrix}]}_{n + 1} .

We may evaluate the largest values for $a$ , $b$ , and $c$ that satisfy the constraint such that $a > b > c \geq 0$ .

$a$	$b$	$c$	$n$

2	1	0	0
3	1	0	1
3	2	0	2
3	2	1	3
4	1	0	4
4	2	0	5
4	2	1	6
4	3	0	7
4	3	1	8
4	3	2	9
5	1	0	10
5	2	0	11
5	2	1	12
5	3	0	13
5	3	1	14
5	3	2	15
5	4	0	16
5	4	1	17
5	4	2	18
5	4	3	19
6	1	0	20

This pattern can be continued for higher values of $n$ by the following method: let $a$ be the largest integer that satisﬁes $(\binom{a}{3}) \leq n$ ; $b$ the largest that satisﬁes $(\binom{b}{2}) \leq n - (\binom{a}{3})$ ; and $c$ that satisﬁes $(\binom{c}{1}) \leq n - (\binom{a}{3}) - (\binom{b}{2})$ .

Proposition. $a_{m} = \frac{{(- 1)}^{m}}{m!} \sum_{1 \leq k} {(- 1)}^{k} (\binom{m - 1}{k - 1}) \ln k$ in Stirling’s generalization of the factorial function.

Proof. Stirling’s generalization of the factorial function is

\ln n! = \sum_{0 \leq m} a_{m + 1} \prod_{0 \leq j \leq m} (n - j) .

We must show that

a_{m} = \frac{{(- 1)}^{m}}{m!} \sum_{1 \leq k} {(- 1)}^{k} (\binom{m - 1}{k - 1}) \ln k .

But given

\sum_{0 \leq j} (\binom{m}{j}) {(- 1)}^{m - j} = \sum_{0 \leq j} (\binom{m}{j}) {(- 1)}^{m - j}

we have

\begin{array}{l} \sum_{0 \leq j} (\binom{m}{j}) {(- 1)}^{m - j} \ln n! & = \sum_{0 \leq j} (\binom{m}{j}) {(- 1)}^{m - j} \sum_{0 \leq k} a_{k + 1} \prod_{0 \leq j \leq k} (n - j) \\ = \sum_{0 \leq j} (\binom{m}{j}) {(- 1)}^{m - j} \sum_{0 \leq k} a_{k + 1} j^{\underset{̲}{k + 1}} & from Eq. 1.2.5-18 \\ = \sum_{0 \leq j} (\binom{m}{j}) {(- 1)}^{m - j} \sum_{0 \leq k} a_{k + 1} \frac{j!}{(j - (k + 1))!} & from Eq. 1.2.5-21 \\ = \sum_{0 \leq j} (\binom{m}{j}) {(- 1)}^{m - j} \sum_{0 \leq k} a_{k + 1} (k + 1)! \frac{j!}{(k + 1)! (j - (k + 1))!} \\ = \sum_{0 \leq j} (\binom{m}{j}) {(- 1)}^{m - j} \sum_{0 \leq k} a_{k + 1} (k + 1)! (\binom{j}{k + 1}) \\ = \sum_{0 \leq j} (\binom{m}{j}) {(- 1)}^{m - j} (\sum_{0 \leq k} a_{k} k! (\binom{j}{k}) - a_{0} 0! (\binom{j}{0})) \\ = \sum_{0 \leq j} (\binom{m}{j}) {(- 1)}^{m - j} (\sum_{0 \leq k} a_{k} k! (\binom{j}{k}) - a_{0}) \\ = \sum_{0 \leq j} (\binom{m}{j}) {(- 1)}^{m - j} (\sum_{0 \leq k} a_{k} k! (\binom{j}{k}) - \frac{{(- 1)}^{0}}{0!} \sum_{1 \leq k} {(- 1)}^{k} (\binom{- 1}{k - 1}) \ln k) \\ = \sum_{0 \leq j} (\binom{m}{j}) {(- 1)}^{m - j} (\sum_{0 \leq k} a_{k} k! (\binom{j}{k}) - 0) \\ = \sum_{0 \leq j} (\binom{m}{j}) {(- 1)}^{m - j} \sum_{0 \leq k} a_{k} k! (\binom{j}{k}) \\ = \sum_{0 \leq j} (\binom{m}{j}) {(- 1)}^{m - j} \sum_{k} k! a_{k} (\binom{j}{k}) \\ = \sum_{k} k! a_{k} \sum j (\binom{j}{k}) (\binom{m}{j}) {(- 1)}^{m - j} \\ = m! a_{m} & from Eq. (33) \end{array}

And so

\begin{array}{l} a_{m} & = \frac{1}{m!} \sum_{0 \leq j} (\binom{m}{j}) {(- 1)}^{m - j} \ln n! \\ = \frac{1}{m!} \sum_{0 \leq j} (\binom{m}{j}) {(- 1)}^{m + j} \ln n! \\ = \frac{{(- 1)}^{m}}{m!} \sum_{0 \leq j} (\binom{m}{j}) {(- 1)}^{j} \ln n! \\ = \frac{{(- 1)}^{m}}{m!} \sum_{0 \leq j} (\binom{m}{j}) {(- 1)}^{j} \sum_{1 \leq k \leq n} \ln k \\ = \frac{{(- 1)}^{m}}{m!} \sum_{0 \leq j} \sum_{1 \leq k \leq n} (\binom{m}{j}) {(- 1)}^{j} \ln k \\ = \frac{{(- 1)}^{m}}{m!} \sum_{1 \leq k} \sum_{k \leq j} (\binom{m}{j}) {(- 1)}^{j} \ln k \\ = \frac{{(- 1)}^{m}}{m!} \sum_{1 \leq k} \ln k \sum_{k \leq j} (\binom{m}{j}) {(- 1)}^{j} \\ = \frac{{(- 1)}^{m}}{m!} \sum_{1 \leq k} \ln k (\sum_{j \leq m} (\binom{m}{j}) {(- 1)}^{j} - \sum_{j \leq k - 1} (\binom{m}{j}) {(- 1)}^{j}) \\ = \frac{{(- 1)}^{m}}{m!} \sum_{1 \leq k} \ln k ({(- 1 + 1)}^{m} - \sum_{j \leq k - 1} (\binom{m}{j}) {(- 1)}^{j}) & from Eq. (13) \\ = \frac{{(- 1)}^{m}}{m!} \sum_{1 \leq k} \ln k (0 - \sum_{j \leq k - 1} (\binom{m}{j}) {(- 1)}^{j}) \\ = \frac{{(- 1)}^{m}}{m!} \sum_{1 \leq k} \ln k (- 1) \sum_{j \leq k - 1} (\binom{m}{j}) {(- 1)}^{j} \\ = \frac{{(- 1)}^{m}}{m!} \sum_{1 \leq k} \ln k (- 1) {(- 1)}^{k - 1} (\binom{m - 1}{k - 1}) & from Eq. (18) \\ = \frac{{(- 1)}^{m}}{m!} \sum_{1 \leq k} {(- 1)}^{k} (\binom{m - 1}{k - 1}) \ln k . \end{array}

Therefore

a_{m} = \frac{{(- 1)}^{m}}{m!} \sum_{1 \leq k} {(- 1)}^{k} (\binom{m - 1}{k - 1}) \ln k

as we needed to show. □

In order to prove the “ $q$ -nomial theorem”, we deﬁne

{(\binom{r}{k})}_{q} = \frac{\prod_{1 \leq j \leq k} (1 - q^{r - j + 1})}{\prod_{1 \leq j \leq k} (1 - q^{j})} = \prod_{1 \leq j \leq k} \frac{1 - q^{r - j + 1}}{1 - q^{j}}

and assume $q$ -nomial symmetry

{(\binom{n}{k})}_{q} = {(\binom{n}{n - k})}_{q}

as well as the two $q$ -Pascal identities

{(\binom{n + 1}{k})}_{q} = {(\binom{n}{k})}_{q} + {(\binom{n}{k - 1})}_{q} q^{n + 1 - k}

and

{(\binom{n + 1}{k})}_{q} = {(\binom{n}{k})}_{q} q^{k} + {(\binom{n}{k - 1})}_{q} .

Proposition. $\prod_{0 \leq k \leq n - 1} (1 + q^{k} x) = \sum_{0 \leq k \leq n} {(\binom{n}{k})}_{q} q^{k (k - 1) ∕ 2} x^{k}$ .

Proof. Let $n$ and $q$ be an arbitrary nonnegative integer and real number, respectively. We must show that

\prod_{0 \leq k \leq n - 1} (1 + q^{k} x) = \sum_{0 \leq k \leq n} {(\binom{n}{k})}_{q} q^{k (k - 1) ∕ 2} x^{k}

If $n = 0$

\begin{array}{l} \prod_{0 \leq k \leq n - 1} (1 + q^{k} x) & = \prod_{0 \leq k \leq - 1} (1 + q^{k} x) \\ = 1 \\ = \frac{1}{1} \\ = \frac{\prod_{1 \leq j \leq 0} (1 - q^{0 - j + 1})}{\prod_{1 \leq j \leq 0} (1 - q^{j})} \\ = {(\binom{0}{0})}_{q} \\ = {(\binom{0}{0})}_{q} q^{(0) (- 1) ∕ 2} x^{0} \\ = \sum_{0 \leq k \leq 0} {(\binom{0}{k})}_{q} q^{k (k - 1) ∕ 2} x^{k} \\ = \sum_{0 \leq k \leq n} {(\binom{n}{k})}_{q} q^{k (k - 1) ∕ 2} x^{k} . \end{array}

Then, assuming

\prod_{0 \leq k \leq n - 1} (1 + q^{k} x) = \sum_{0 \leq k \leq n} {(\binom{n}{k})}_{q} q^{k (k - 1) ∕ 2} x^{k}

we must show that

\prod_{0 \leq k \leq n} (1 + q^{k} x) = \sum_{0 \leq k \leq n + 1} {(\binom{n + 1}{k})}_{q} q^{k (k - 1) ∕ 2} x^{k} .

But

\begin{array}{l} \prod_{0 \leq k \leq n} (1 + q^{k} x) & = (1 + q^{n} x) \prod_{0 \leq k \leq n - 1} (1 + q^{k} x) \\ = (1 + q^{n} x) \sum_{0 \leq k \leq n} {(\binom{n}{k})}_{q} q^{k (k - 1) ∕ 2} x^{k} \\ = \sum_{0 \leq k \leq n} {(\binom{n}{k})}_{q} q^{k (k - 1) ∕ 2} x^{k} + q^{n} x \sum_{0 \leq k \leq n} {(\binom{n}{k})}_{q} q^{k (k - 1) ∕ 2} x^{k} \\ = \sum_{0 \leq k \leq n} {(\binom{n}{k})}_{q} q^{k (k - 1) ∕ 2} x^{k} + \sum_{0 \leq k \leq n} {(\binom{n}{k})}_{q} q^{n + k (k - 1) ∕ 2} x^{k + 1} \\ = \sum_{0 \leq k \leq n} {(\binom{n}{k})}_{q} q^{k (k - 1) ∕ 2} x^{k} + \sum_{1 \leq k \leq n + 1} {(\binom{n}{k - 1})}_{q} q^{n + (k - 1) (k - 2) ∕ 2} x^{k} \\ = \sum_{0 \leq k \leq n + 1} {(\binom{n}{k})}_{q} q^{k (k - 1) ∕ 2} x^{k} + \sum_{0 \leq k \leq n + 1} {(\binom{n}{k - 1})}_{q} q^{n + (k - 1) (k - 2) ∕ 2} x^{k} \\ = \sum_{0 \leq k \leq n + 1} ({(\binom{n}{k})}_{q} + {(\binom{n}{k - 1})}_{q} q^{n + (k - 1) (k - 2) ∕ 2 - k (k - 1) ∕ 2}) q^{k (k - 1) ∕ 2} x^{k} \\ = \sum_{0 \leq k \leq n + 1} ({(\binom{n}{k})}_{q} + {(\binom{n}{k - 1})}_{q} q^{n + 1 - k}) q^{k (k - 1) ∕ 2} x^{k} \\ = \sum_{0 \leq k \leq n + 1} {(\binom{n + 1}{k})}_{q} q^{k (k - 1) ∕ 2} x^{k} . \end{array}

Hence

\prod_{0 \leq k \leq n - 1} (1 + q^{k} x) = \sum_{0 \leq k \leq n} {(\binom{n}{k})}_{q} q^{k (k - 1) ∕ 2} x^{k}

as we needed to show. □

We may also ﬁnd $q$ -nomial generalizations of the fundamental identities (17) and (21).

For (17), we have

\begin{array}{l} {(\binom{r}{k})}_{q} & = \prod_{1 \leq j \leq k} \frac{1 - q^{r - j + 1}}{1 - q^{j}} \\ = \prod_{1 \leq j \leq k} \frac{- 1}{- 1} \frac{1 - q^{r - j + 1}}{1 - q^{j}} \\ = {(- 1)}^{k} \prod_{1 \leq j \leq k} - \frac{1 - q^{r - j + 1}}{1 - q^{j}} \\ = {(- 1)}^{k} \prod_{1 \leq j \leq k} q^{r - j + 1} \frac{1 - q^{- r + j - 1}}{1 - q^{j}} \\ = {(- 1)}^{k} (\prod_{1 \leq j \leq k} \frac{q^{r - j + 1}}{1 - q^{j}}) (\prod_{1 \leq j \leq k} 1 - q^{- r + j - 1}) \\ = {(- 1)}^{k} (\prod_{1 \leq j \leq k} \frac{q^{r - j + 1}}{1 - q^{j}}) (\prod_{1 \leq - j + k + 1 \leq k} 1 - q^{- r + j - 1}) \\ = {(- 1)}^{k} (\prod_{1 \leq j \leq k} \frac{q^{r - j + 1}}{1 - q^{j}}) (\prod_{1 \leq - j + k + 1 \leq k} 1 - q^{k - r - (- j + k + 1)}) \\ = {(- 1)}^{k} (\prod_{1 \leq j \leq k} \frac{q^{r - j + 1}}{1 - q^{j}}) (\prod_{1 \leq j \leq k} 1 - q^{k - r - j}) \\ = {(- 1)}^{k} \prod_{1 \leq j \leq k} q^{r - j + 1} \frac{1 - q^{k - r - j}}{1 - q^{j}} \\ = {(- 1)}^{k} \frac{\prod_{1 \leq j \leq k} q^{r}}{\prod_{1 \leq j \leq k} q^{j - 1}} \prod_{1 \leq j \leq k} \frac{1 - q^{k - r - j}}{1 - q^{j}} \\ = {(- 1)}^{k} \frac{q^{k r}}{\sqrt{{(q^{1 - 1} q^{k - 1})}^{k}}} \prod_{1 \leq j \leq k} \frac{1 - q^{k - r - j}}{1 - q^{j}} \\ = {(- 1)}^{k} \frac{q^{k r}}{q^{k (k - 1) ∕ 2}} \prod_{1 \leq j \leq k} \frac{1 - q^{k - r - j}}{1 - q^{j}} \\ = {(- 1)}^{k} q^{k r - k (k - 1) ∕ 2} \prod_{1 \leq j \leq k} \frac{1 - q^{k - r - j}}{1 - q^{j}} \\ = {(- 1)}^{k} q^{k r - k (k - 1) ∕ 2} \prod_{1 \leq j \leq k} \frac{1 - q^{k - r - 1 - j + 1}}{1 - q^{j}} \\ = {(- 1)}^{k} q^{k r - k (k - 1) ∕ 2} {(\binom{k - r - 1}{k})}_{q} \\ = {(- 1)}^{k} {(\binom{k - r - 1}{k})}_{q} q^{k r - k (k - 1) ∕ 2} \end{array}

so that the $q$ -nomial generalizations of the fundamental identity (17) is

{(\binom{r}{k})}_{q} = {(- 1)}^{k} {(\binom{k - r - 1}{k})}_{q} q^{k r - k (k - 1) ∕ 2} .

For (21), the $q$ -nomial theorem

\prod_{0 \leq k \leq n - 1} (1 + q^{k} x) = \sum_{0 \leq k \leq n} {(\binom{n}{k})}_{q} q^{k (k - 1) ∕ 2} x^{k}

gives us

\begin{array}{l} \sum_{0 \leq n \leq r + s} {(\binom{r + s}{n})}_{q} q^{n (n - 1) ∕ 2} x^{n} \\ = \prod_{0 \leq n \leq r + s - 1} (1 + q^{n} x) \\ = \prod_{0 \leq k \leq r - 1} (1 + q^{k} x) \prod_{r \leq k \leq r + s - 1} (1 + q^{k} x) \\ = \prod_{0 \leq k \leq r - 1} (1 + q^{k} x) \prod_{0 \leq k - r \leq s - 1} (1 + q^{k} x) \\ = \prod_{0 \leq k \leq r - 1} (1 + q^{k} x) \prod_{0 \leq k \leq s - 1} (1 + q^{k + r} x) \\ = \prod_{0 \leq k \leq r - 1} (1 + q^{k} x) \prod_{0 \leq k \leq s - 1} (1 + q^{k} q^{r} x) \\ = (\sum_{0 \leq k \leq r} {(\binom{r}{k})}_{q} q^{k (k - 1) ∕ 2} x^{k}) (\sum_{0 \leq k \leq s} {(\binom{s}{k})}_{q} q^{k (k - 1) ∕ 2} {(q^{r} x)}^{k}) \\ = (\sum_{0 \leq k \leq r} {(\binom{r}{k})}_{q} q^{k (k - 1) ∕ 2} x^{k}) (\sum_{0 \leq k \leq s} {(\binom{s}{k})}_{q} q^{k (k - 1) ∕ 2} q^{r k} x^{k}) \\ = (\sum_{0 \leq k \leq r} {(\binom{r}{k})}_{q} q^{k (k - 1) ∕ 2} x^{k}) (\sum_{0 \leq n - k \leq s} {(\binom{s}{n - k})}_{q} q^{(n - k) (n - k - 1) ∕ 2} q^{r (n - k)} x^{n - k}) \\ = \sum_{0 \leq n \leq r + s} (\sum_{0 \leq k \leq r} {(\binom{r}{k})}_{q} {(\binom{s}{n - k})}_{q} q^{k (k - 1) ∕ 2} q^{(n - k) (n - k - 1) ∕ 2} q^{r (n - k)}) x^{n} \\ = \sum_{0 \leq n \leq r + s} (\sum_{0 \leq k \leq r} {(\binom{r}{k})}_{q} {(\binom{s}{n - k})}_{q} q^{k^{2} ∕ 2 - k ∕ 2 + n^{2} ∕ 2 - n k ∕ 2 - k n ∕ 2 + k^{2} ∕ 2 - n ∕ 2 + k ∕ 2 + r n - r k}) x^{n} \\ = \sum_{0 \leq n \leq r + s} (\sum_{0 \leq k \leq r} {(\binom{r}{k})}_{q} {(\binom{s}{n - k})}_{q} q^{k^{2} + n^{2} ∕ 2 - n k - n ∕ 2 + r n - r k}) x^{n} . \end{array}

Equating coeﬃcients yields

{(\binom{r + s}{n})}_{q} q^{n (n - 1) ∕ 2} = \sum_{0 \leq k \leq r} {(\binom{r}{k})}_{q} {(\binom{s}{n - k})}_{q} q^{k^{2} + n^{2} ∕ 2 - n k - n ∕ 2 + r n - r k}

if and only if

\begin{array}{l} {(\binom{r + s}{n})}_{q} & = \sum_{0 \leq k \leq r} {(\binom{r}{k})}_{q} {(\binom{s}{n - k})}_{q} q^{k^{2} + n^{2} ∕ 2 - n k - n ∕ 2 + r n - r k} / q^{n (n - 1) ∕ 2} \\ = \sum_{0 \leq k \leq r} {(\binom{r}{k})}_{q} {(\binom{s}{n - k})}_{q} q^{k^{2} + n^{2} ∕ 2 - n k - n ∕ 2 + r n - r k - n^{2} ∕ 2 + n ∕ 2} \\ = \sum_{0 \leq k \leq r} {(\binom{r}{k})}_{q} {(\binom{s}{n - k})}_{q} q^{k^{2} - n k + r n - r k} \\ = \sum_{0 \leq k \leq r} {(\binom{r}{k})}_{q} {(\binom{s}{n - k})}_{q} q^{(r - k) (n - k)} \\ = \sum_{0 \leq k \leq s} {(\binom{s}{k})}_{q} {(\binom{r}{n - k})}_{q} q^{(s - k) (n - k)} \\ = \sum_{0 \leq k \leq r} {(\binom{r}{k})}_{q} {(\binom{s}{n - k})}_{q} q^{(s - n + k) k} \end{array}

so that the $q$ -nomial generalizations of the fundamental identity (21) is

{(\binom{r + s}{n})}_{q} = \sum_{0 \leq k \leq r} {(\binom{r}{k})}_{q} {(\binom{s}{n - k})}_{q} q^{(r - k) (n - k)} = \sum_{0 \leq k \leq r} {(\binom{r}{k})}_{q} {(\binom{s}{n - k})}_{q} q^{(s - n + k) k} .

______________________________________________________________________________________________________________________________

H. A. Rothe, Systematisches Lehrbuch der Arithmetik (Leipzig: 1811), xxix; F. Schweins, Analysis (Heidelberg: 1820), §151; D. E. Knuth, J. Combinatorial Theory A10 (1971), 178–180; G. Gasper and M. Rahman, Basic Hypergeometric Series (Cambridge Univ. Press, 1990); C. F. Gauss, Commentationes societatis regiæ scientiarum Gottingensis recentiores 1 (1808), 147–186; Cauchy, Comptes Rendus Acad. Sci. 17 (Paris, 1843), 523–531; C. G. J. Jacobi, Crelle 32 (1846), 197–204; E. Heine, Crelle 34 (1847), 285–328.

We have that

A_{n k} = (n + 1) (\binom{n}{k}) - (\binom{n}{k + 1})

and may prove this by induction.

Proposition. $A_{n k} = (n + 1) (\binom{n}{k}) - (\binom{n}{k + 1})$ .

Proof. Let $n$ and $k$ be arbitrary integers such that $n \geq 0$ , $k \geq 0$ , and $n k > 0$ . We must show that

A_{n k} = (n + 1) (\binom{n}{k}) - (\binom{n}{k + 1}) .

First note that

A_{n 0} = (n + 1) (\binom{n}{0}) - (\binom{n}{0 + 1}) = n + 1 - n = 1

and

A_{0 k} = (0 + 1) (\binom{0}{k}) - (\binom{0}{k + 1}) = δ_{0 k}

as required. If $n = 1$ , we have

\begin{array}{l} A_{1 k} & = A_{0 k} + A_{0 (k - 1)} + (\binom{1}{k}) \\ = δ_{0 k} + δ_{0 (k - 1)} + (\binom{1}{k}) \\ = (\binom{0}{k}) - (\binom{0}{k + 1}) + (\binom{0}{k - 1}) - (\binom{0}{k}) + (\binom{1}{k}) \\ = (\binom{0}{k}) + (\binom{0}{k - 1}) + (\binom{1}{k}) - ((\binom{0}{k + 1}) + (\binom{0}{k})) \\ = (\binom{1}{k}) + (\binom{1}{k}) - (\binom{1}{k + 1}) \\ = 2 (\binom{1}{k}) - (\binom{1}{k + 1}) \\ = (1 + 1) (\binom{1}{k}) - (\binom{1}{k + 1}) . \end{array}

Then, assuming

A_{n k} = (n + 1) (\binom{n}{k}) - (\binom{n}{k + 1})

we must show that

A_{(n + 1) k} = ((n + 1) + 1) (\binom{n + 1}{k}) - (\binom{n + 1}{k + 1}) .

But

\begin{array}{l} A_{(n + 1) k} & = A_{n k} + A_{n (k - 1)} + (\binom{n + 1}{k}) \\ = (n + 1) (\binom{n}{k}) - (\binom{n}{k + 1}) + (n + 1) (\binom{n}{k - 1}) - (\binom{n}{k}) + (\binom{n + 1}{k}) \\ = (n + 1) ((\binom{n}{k}) + (\binom{n}{k - 1})) + (\binom{n + 1}{k}) - ((\binom{n}{k + 1}) + (\binom{n}{k})) \\ = (n + 1) (\binom{n + 1}{k}) + (\binom{n + 1}{k}) - (\binom{n + 1}{k + 1}) \\ = (n + 2) (\binom{n + 1}{k}) - (\binom{n + 1}{k + 1}) \\ = ((n + 1) + 1) (\binom{n + 1}{k}) - (\binom{n + 1}{k + 1}) \end{array}

as we needed to show. □

The number of $k$ -combinations of $n$ objects, if repetition is allowed, is given by

(\binom{n + k - 1}{k}) .

The number of $k$ -combinations of $n$ objects, if repetition is not allowed is simply the number of integer solutions $(o_{1}, o_{2}, \dots, o_{k})$ such that $0 < o_{1} < o_{2} < \dots < o_{k} < n + 1$ , known to be

| {o_{i} : 0 < o_{1} < o_{2} < \dots < o_{k} < n + 1} | = (\binom{n}{k}) .

If repetitions are allowed, we want to determine

\begin{array}{l} | {o_{i} : 0 < o_{1} \leq o_{2} \leq \dots \leq o_{k} < n + 1} | \\ = | {o_{i} : 0 < o_{1} < o_{2} + 1 < \dots < o_{k} + k - 1 < n + k - 1 + 1} | \\ = | {o_{i}^{'} : 0 < o_{1}^{'} < o_{2}^{'} < \dots < o_{k}^{'} < n + k} | \\ = (\binom{n + k - 1}{k}) \end{array}

and hence the result.

________________________________________________________________________________

H. F. Sherk, Crelle 3 (1828), 97; W. A. Förstemann, Crelle 13 (1835), 237.

We have

\begin{array}{l} \sum_{k} [\binom{n + 1}{k + 1}] \{\binom{k}{m}\} {(- 1)}^{k - m} \\ = \sum_{k} (n [\binom{n}{k + 1}] + [\binom{n}{k}]) \{\binom{k}{m}\} {(- 1)}^{k - m} & from Eq. (46) \\ = n \sum_{k} [\binom{n}{k + 1}] \{\binom{k}{m}\} {(- 1)}^{k - m} + \sum_{k} [\binom{n}{k}] \{\binom{k}{m}\} {(- 1)}^{k - m} \\ = n \sum_{k} [\binom{n}{k + 1}] \{\binom{k}{m}\} {(- 1)}^{k - m} + {(- 1)}^{n - m} \sum_{k} [\binom{n}{k}] \{\binom{k}{m}\} {(- 1)}^{n - k} \\ = n \sum_{k} [\binom{n}{k + 1}] \{\binom{k}{m}\} {(- 1)}^{k - m} + {(- 1)}^{n - m} δ_{m n} & from Eq. (47) \\ = n \sum_{k} [\binom{n}{k + 1}] \{\binom{k}{m}\} {(- 1)}^{k - m} + δ_{m n} . \end{array}

If $n < m$ then $k < m$ and

n \sum_{k} [\binom{n}{k + 1}] \{\binom{k}{m}\} {(- 1)}^{k - m} + δ_{m n} = 0 + 0 = 0 .

If $n = m$ then $k < m$ and

n \sum_{k} [\binom{n}{k + 1}] \{\binom{k}{m}\} {(- 1)}^{k - m} + δ_{m n} = 0 + 1 = 1 .

Otherwise, if $n > m$

n \sum_{k} [\binom{n}{k + 1}] \{\binom{k}{m}\} {(- 1)}^{k - m} + δ_{m n} = n \sum_{k} [\binom{n}{k + 1}] \{\binom{k}{m}\} {(- 1)}^{k - m} = n! ∕ m!

which we may prove by induction.

Proposition. $n \sum_{k} [\binom{n}{k + 1}] \{\binom{k}{m}\} {(- 1)}^{k - m} = n! ∕ m!$ for $0 \leq m < n$ .

Proof. Let $m$ and $n$ be arbitrary nonnegative integers such that $m < n$ . We must show that

n \sum_{k} [\binom{n}{k + 1}] \{\binom{k}{m}\} {(- 1)}^{k - m} = n! ∕ m!

If $n = 1$ , $0 \leq m < n = 1 \Rightarrow m = 0$ and

\begin{array}{l} n \sum_{k} [\binom{n}{k + 1}] \{\binom{k}{m}\} {(- 1)}^{k - m} \\ = \sum_{k} [\binom{1}{k + 1}] \{\binom{k}{0}\} {(- 1)}^{k} \\ = \sum_{k} [\binom{1}{k + 1}] \{\binom{k}{0}\} {(- 1)}^{k} \\ = [\binom{1}{1}] \{\binom{0}{0}\} {(- 1)}^{0} \\ = 1 \\ = 1! ∕ 0! \\ = n! ∕ m! \end{array}

Then, assuming

n \sum_{k} [\binom{n}{k + 1}] \{\binom{k}{m}\} {(- 1)}^{k - m} = n! ∕ m!

we must show that

(n + 1) \sum_{k} [\binom{n + 1}{k + 1}] \{\binom{k}{m}\} {(- 1)}^{k - m} = (n + 1)! ∕ m!

But

\begin{array}{l} (n + 1) \sum_{k} [\binom{n + 1}{k + 1}] \{\binom{k}{m}\} {(- 1)}^{k - m} \\ = (n + 1) \sum_{k} (n [\binom{n}{k + 1}] + [\binom{n}{k}]) \{\binom{k}{m}\} {(- 1)}^{k - m} \\ = (n + 1) \sum_{k} n [\binom{n}{k + 1}] \{\binom{k}{m}\} {(- 1)}^{k - m} + (n + 1) \sum_{k} [\binom{n}{k}] \{\binom{k}{m}\} {(- 1)}^{k - m} \\ = (n + 1) n \sum_{k} [\binom{n}{k + 1}] \{\binom{k}{m}\} {(- 1)}^{k - m} + (n + 1) \sum_{k} [\binom{n}{k}] \{\binom{k}{m}\} {(- 1)}^{k - m} \\ = (n + 1) n! ∕ m! + (n + 1) \sum_{k} [\binom{n}{k}] \{\binom{k}{m}\} {(- 1)}^{k - m} \\ = (n + 1) n! ∕ m! + (n + 1) \sum_{k} [\binom{n}{k}] \{\binom{k}{m}\} {(- 1)}^{n - k} {(- 1)}^{k - m - n + k} \\ = (n + 1) n! ∕ m! + (n + 1) {(- 1)}^{m + n} \sum_{k} [\binom{n}{k}] \{\binom{k}{m}\} {(- 1)}^{n - k} \\ = (n + 1) n! ∕ m! + (n + 1) {(- 1)}^{m + n} δ_{m n} & from Eq. (47) \\ = (n + 1) n! ∕ m! + 0 \\ = (n + 1) n! ∕ m! \\ = (n + 1)! ∕ m! \end{array}

as we needed to show. □

And so, since

\begin{array}{l} \sum_{k} [\binom{n + 1}{k + 1}] \{\binom{k}{m}\} {(- 1)}^{k - m} = \{\begin{matrix} 0 & if n < m \\ 1 & if n = m \\ n! ∕ m! & otherwise \end{matrix} \end{array}

we have that

\sum_{k} [\binom{n + 1}{k + 1}] \{\binom{k}{m}\} {(- 1)}^{k - m} = [n \geq m] n! ∕ m!

Proposition. $\sum_{k} {(- 1)}^{k} (\binom{l + m}{l + k}) (\binom{m + n}{m + k}) (\binom{n + l}{n + k}) = \frac{(l + m + n)!}{l! m! n!}$ , integer $l, m, n \geq 0$ .

Proof. Let $l, m, n$ be arbitrary nonnegative integers. We must show that

\sum_{k} {(- 1)}^{k} (\binom{l + m}{l + k}) (\binom{m + n}{m + k}) (\binom{n + l}{n + k}) = \frac{(l + m + n)!}{l! m! n!} .

But from exercise 31

\sum_{k} (\binom{m - r + s}{k}) (\binom{n + r - s}{n - k}) (\binom{r + k}{m + n}) = (\binom{r}{m}) (\binom{s}{n})

we have for $m^{'} = m + k, n^{'} = l - k, r^{'} = m + n, s^{'} = n + l, k^{'} = j$ that

\begin{array}{l} \sum_{k} {(- 1)}^{k} (\binom{l + m}{l + k}) (\binom{m + n}{m + k}) (\binom{n + l}{n + k}) \\ = \sum_{k} {(- 1)}^{k} (\binom{l + m}{l + k}) (\binom{r^{'}}{m^{'}}) (\binom{s^{'}}{s^{'} - n^{'}}) \\ = \sum_{k} {(- 1)}^{k} (\binom{l + m}{l + k}) (\binom{r^{'}}{m^{'}}) (\binom{s^{'}}{n^{'}}) \\ = \sum_{k} {(- 1)}^{k} (\binom{l + m}{l + k}) \sum_{k^{'}} (\binom{m^{'} - r^{'} + s^{'}}{k^{'}}) (\binom{n^{'} + r^{'} - s^{'}}{n^{'} - k^{'}}) (\binom{r^{'} + k^{'}}{m^{'} + n^{'}}) \\ = \sum_{k} {(- 1)}^{k} (\binom{l + m}{l + k}) \sum_{j} (\binom{m + k - m - n + n + l}{j}) (\binom{l - k + m + n - n - l}{l - k - j}) (\binom{m + n + j}{m + k + l - k}) \\ = \sum_{k, j} {(- 1)}^{k} (\binom{l + m}{l + k}) (\binom{l + k}{j}) (\binom{m - k}{l - k - j}) (\binom{m + n + j}{m + l}) \\ = \sum_{k, j} {(- 1)}^{k} \frac{(l + m)!}{(m - k)! (l + k)!} \frac{(l + k)!}{(l + k - j)! j!} \frac{(m - k)!}{(m - l + j)! (l - k - j)!} \frac{(m + n + j)!}{(n + j - l)! (m + l)!} \\ = \sum_{k, j} {(- 1)}^{k} \frac{1}{(l + k - j)! j!} \frac{1}{(m - l + j)! (l - k - j)!} \frac{(m + n + j)!}{(n + j - l)!} \\ = \sum_{k, j} {(- 1)}^{k} \frac{1}{(l - j - k)! (l - j + k)!} \frac{(m + n + j)!}{j! (m - l + j)! (n + j - l)!} \\ = \sum_{k, j} {(- 1)}^{k} \frac{(2 l - 2 j)!}{(2 l - 2 j - (l - j + k))! (l - j + k)! (2 l - 2 j)!} \frac{(m + n + j)!}{j! (m - l + j)! (n + j - l)!} \\ = \sum_{k, j} {(- 1)}^{k} (\binom{2 l - 2 j}{l - j + k}) \frac{(m + n + j)!}{(2 l - 2 j)! j! (m - l + j)! (n + j - l)!} \\ = \sum_{k, j} {(- 1)}^{k} (\binom{2 l - 2 j}{l - j + k}) \frac{1}{(2 (l - j))!} \frac{(m + n + j)!}{j! (m - l + j)! (n + j - l)!} \\ = \sum_{k, j} {(- 1)}^{k} (\binom{2 l - 2 j}{l - j + k}) (0 - 2 (l - j))! \frac{0!}{(2 (l - j))! (0 - 2 (l - j))!} \frac{(m + n + j)!}{j! (m - l + j)! (n + j - l)!} \\ = \sum_{k, j} {(- 1)}^{k} (\binom{2 l - 2 j}{l - j + k}) (2 (j - l))! (\binom{0}{2 (l - j)}) \frac{(m + n + j)!}{j! (m - l + j)! (n + j - l)!} \\ = \sum_{k, j} {(- 1)}^{k} (\binom{2 l - 2 j}{l - j + k}) (2 (j - l))! δ_{l j} \frac{(m + n + j)!}{j! (m - l + j)! (n + j - l)!} \\ = \sum_{k} {(- 1)}^{k} (\binom{2 l - 2 l}{l - l + k}) (2 (l - l))! \frac{(m + n + l)!}{l! (m - l + l)! (n + l - l)!} \\ = \sum_{k} {(- 1)}^{k} (\binom{0}{k}) 0! \frac{(m + n + l)!}{l! m! n!} \\ = {(- 1)}^{0} \frac{(l + m + n)!}{l! m! n!} \\ = \frac{(l + m + n)!}{l! m! n!} \end{array}

as we needed to show. □

______________________________________________________________________________________________________________________________

A. C. Dixon, Messenger of Math. 20 (1891), 79–80; A. C. Dixon, Proc. London Math. Soc. 35 (1903), 285–289; L. J. Rogers, Proc. London Math. Soc. 26 (1895), 15–32, §8; P. A. MacMahon, Quarterly Journal of Pure and Applied Math. 33 (1902), 274–288; John Dougall, Proc. Edinburgh Math. Society 25 (1907), 114–132.

Proposition. $\sum_{j, k} {(- 1)}^{j + k} (\binom{j + k}{k + l}) (\binom{r}{j}) (\binom{n}{k}) (\binom{s + n - j - k}{m - j}) = {(- 1)}^{l} (\binom{n + r}{n + l}) (\binom{s - r}{m - n - l})$ , integers $l$ , $m$ , and $n \geq 0$ .

Proof. Let $l$ , $m$ , and $n$ be arbitrary integers such that $n \geq 0$ . We must show that

\sum_{j, k} {(- 1)}^{j + k} (\binom{j + k}{k + l}) (\binom{r}{j}) (\binom{n}{k}) (\binom{s + n - j - k}{m - j}) = {(- 1)}^{l} (\binom{n + r}{n + l}) (\binom{s - r}{m - n - l}) .

But as a polynomial in arbitary reals $x$ and $y$ , we have

\begin{array}{l} \sum_{l, m} \sum_{j, k} {(- 1)}^{j + k} (\binom{j + k}{l + k}) (\binom{r}{j}) (\binom{n}{k}) (\binom{s + n - j - k}{m - j}) x^{l} y^{m} \\ = \sum_{m} \sum_{j, k} {(- 1)}^{j + k} \sum_{l} (\binom{j + k}{l + k}) x^{l} (\binom{r}{j}) (\binom{n}{k}) (\binom{s + n - j - k}{m - j}) y^{m} \\ = \sum_{m} \sum_{j, k} {(- 1)}^{j + k} \sum_{l + k} (\binom{j + k}{l + k}) x^{l} (\binom{r}{j}) (\binom{n}{k}) (\binom{s + n - j - k}{m - j}) y^{m} \\ = \sum_{m} \sum_{j, k} {(- 1)}^{j + k} \sum_{l + k} (\binom{j + k}{l + k}) \frac{x^{l + k}}{x^{k}} (\binom{r}{j}) (\binom{n}{k}) (\binom{s + n - j - k}{m - j}) y^{m} \\ = \sum_{m} \sum_{j, k} {(- 1)}^{j + k} \frac{{(1 + x)}^{j + k}}{x^{k}} (\binom{r}{j}) (\binom{n}{k}) (\binom{s + n - j - k}{m - j}) y^{m} \\ = \sum_{j, k} {(- 1)}^{j + k} \frac{{(1 + x)}^{j + k}}{x^{k}} (\binom{r}{j}) (\binom{n}{k}) \sum_{m} (\binom{s + n - j - k}{m - j}) y^{m} \\ = \sum_{j, k} {(- 1)}^{j + k} \frac{{(1 + x)}^{j + k}}{x^{k}} (\binom{r}{j}) (\binom{n}{k}) \sum_{m - j} (\binom{s + n - j - k}{m - j}) y^{m} \\ = \sum_{j, k} {(- 1)}^{j + k} \frac{{(1 + x)}^{j + k}}{x^{k}} (\binom{r}{j}) (\binom{n}{k}) \sum_{m - j} (\binom{s + n - j - k}{m - j}) y^{m - j} y^{j} \\ = \sum_{j, k} {(- 1)}^{j + k} \frac{{(1 + x)}^{j + k}}{x^{k}} (\binom{r}{j}) (\binom{n}{k}) {(1 + y)}^{s + n - j - k} y^{j} \\ = \sum_{j} (\binom{r}{j}) {(- 1)}^{j} \frac{{(1 + x)}^{j} y^{j}}{{(1 + y)}^{j}} \sum_{k} (\binom{n}{k}) {(- 1)}^{k} \frac{{(1 + x)}^{k}}{{(1 + y)}^{k} x^{k}} {(1 + y)}^{s + n} \\ = \sum_{j} (\binom{r}{j}) {(- \frac{(1 + x) y}{1 + y})}^{j} \sum_{k} (\binom{n}{k}) {(- \frac{1 + x}{(1 + y) x})}^{k} {(1 + y)}^{s + n} \\ = {(1 - \frac{(1 + x) y}{1 + y})}^{r} {(1 - \frac{1 + x}{(1 + y) x})}^{n} {(1 + y)}^{s + n} \\ = {(\frac{1 + y - (1 + x) y}{1 + y})}^{r} {(\frac{(1 + y) x - (1 + x)}{(1 + y) x})}^{n} {(1 + y)}^{s + n} \\ = {(\frac{1 - x y}{1 + y})}^{r} {(\frac{(- 1) (1 - x y)}{(1 + y) x})}^{n} {(1 + y)}^{s + n} \\ = \frac{{(1 - x y)}^{r}}{{(1 + y)}^{r}} \frac{{(- 1)}^{n} {(1 - x y)}^{n}}{{(1 + y)}^{n} x^{n}} {(1 + y)}^{s + n} \\ = \frac{{(1 - x y)}^{r}}{{(1 + y)}^{r}} \frac{{(- 1)}^{n} {(1 - x y)}^{n}}{x^{n}} {(1 + y)}^{s} \\ = \frac{{(- 1)}^{n} {(1 - x y)}^{n + r} {(1 + y)}^{s - r}}{x^{n}} . \end{array}

Continuing,

\begin{array}{l} \frac{{(- 1)}^{n} {(1 - x y)}^{n + r} {(1 + y)}^{s - r}}{x^{n}} \\ = \frac{{(- 1)}^{n} \sum_{n + l} (\binom{n + r}{n + l}) {(- x y)}^{n + l} {(1 + y)}^{s - r}}{x^{n}} \\ = \frac{{(- 1)}^{n} \sum_{l} (\binom{n + r}{n + l}) {(- x y)}^{n + l} {(1 + y)}^{s - r}}{x^{n}} \\ = \sum_{l} {(- 1)}^{2 n + l} (\binom{n + r}{n + l}) {(1 + y)}^{s - r} x^{l} y^{n + l} \\ = \sum_{l} {(- 1)}^{l} (\binom{n + r}{n + l}) {(1 + y)}^{s - r} x^{l} y^{n + l} \\ = \sum_{l} {(- 1)}^{l} (\binom{n + r}{n + l}) \sum_{m - n - l} (\binom{s - r}{m - n - l}) y^{m - n - l} x^{l} y^{n + l} \\ = \sum_{l} {(- 1)}^{l} (\binom{n + r}{n + l}) \sum_{m} (\binom{s - r}{m - n - l}) y^{m - n - l} x^{l} y^{n + l} \\ = \sum_{l, m} {(- 1)}^{l} (\binom{n + r}{n + l}) (\binom{s - r}{m - n - l}) x^{l} y^{m} . \end{array}

Equating coeﬃcients yields the result

\sum_{j, k} {(- 1)}^{j + k} (\binom{j + k}{k + l}) (\binom{r}{j}) (\binom{n}{k}) (\binom{s + n - j - k}{m - j}) = {(- 1)}^{l} (\binom{n + r}{n + l}) (\binom{s - r}{m - n - l})

as we needed to show. □

______________________________________________________________________________________________________________________________

CMath, exercises 5.83 and 5.106.

Let $p (n, m)$ denote the number of ways to partition a set of $n$ elements into $m$ nonempty disjoint subsets for nonnegative integers $m$ , $n$ . If $n = 0$ , then clearly

p (0, m) = δ_{0 m} = \{\binom{0}{m}\} .

Otherwise, if $n > 0$ , we seek the number of partitions which contain the set $n$ , given by $p (n - 1, m - 1)$ and the number of partitions in which $n$ has been inserted into sets with other elements, given by $m p (n - 1, m)$ . That is, from Eq. (46) and induction,

p (n, m) = p (n - 1, m - 1) + m p (n - 1, m) = \{\binom{n}{m}\},

and hence the claim.

We may prove Eq. (59).

Proposition. $z^{r} = \sum_{k} \{\binom{r}{r - k}\} z^{\underset{̲}{r - k}}$ for $Re (z) > 0$ .

Proof. Let $r, z$ be arbitrary complex numbers such that $Re (z) > 0$ . We must show that

z^{r} = \sum_{k} \{\binom{r}{r - k}\} z^{\underset{̲}{r - k}} .

In the case that $Re (r) < 1$ , by deﬁnition and since $Re (z) > 0$ ,

\begin{array}{l} Γ (1 - r) & = \int_{0}^{\infty} e^{- t} t^{1 - r - 1} d t \\ = \int_{0}^{\infty} e^{- t} t^{- r} d t \\ = \frac{z^{r - 1}}{z^{r - 1}} \int_{0}^{\infty} e^{- t} t^{- r} d t \\ = \frac{1}{z^{r - 1}} \int_{0}^{\infty} z^{r - 1} e^{- t} t^{- r} d t \\ = \frac{1}{z^{r - 1}} \int_{0}^{\infty} z^{r - 1} e^{- z t} {(z t)}^{- r} d z t \\ = \frac{1}{z^{r - 1}} \int_{0}^{\infty} z^{r - 1 - r + 1} e^{- z t} t^{- r} d t \\ = \frac{1}{z^{r - 1}} \int_{0}^{\infty} e^{- z t} t^{- r} d t \end{array}

if and only if

\begin{array}{l} z^{r} & = \frac{z}{Γ (1 - r)} \int_{0}^{\infty} e^{- z t} t^{- r} d t \\ = \frac{z}{Γ (1 - r)} \int_{0}^{1} {(1 - u)}^{z} {(- \ln (1 - u))}^{- r} d (- \ln (1 - u)) & for e^{- t} = 1 - u \\ = \frac{z}{Γ (1 - r)} \int_{0}^{1} {(1 - u)}^{z - 1} {(\ln (\frac{1}{1 - u}))}^{- r} d u \\ = \frac{z}{Γ (1 - r)} \int_{0}^{1} {(1 - u)}^{z - 1} \frac{u^{- r}}{u^{- r}} {(\ln (\frac{1}{1 - u}))}^{- r} d u \\ = \frac{z}{Γ (1 - r)} \int_{0}^{1} {(1 - u)}^{z - 1} u^{- r} {(\frac{1}{u} \ln (\frac{1}{1 - u}))}^{- r} d u . \end{array}

From Eq. (6.51)¹

\begin{array}{l} {(\frac{1}{u} \ln (\frac{1}{1 - u}))}^{- r} & = - r \sum_{k} [\binom{- r + k}{- r}] \frac{u^{k}}{{(- r + k)}^{\underset{̲}{k + 1}}} \\ = - r \sum_{k} \{\binom{r}{r - k}\} \frac{u^{k}}{{(- r + k)}^{\underset{̲}{k + 1}}} \\ = - r \sum_{k} \{\binom{r}{r - k}\} \frac{Γ (- r) u^{k}}{Γ (- r + k + 1)} \\ = \sum_{k} \{\binom{r}{r - k}\} \frac{Γ (1 - r) u^{k}}{Γ (- r + k + 1)} \end{array}

and given the deﬁnition of the $β$ function as

\int_{0}^{\infty} {(1 - u)}^{z - 1} u^{k - r} d u = β (k - r + 1, z) = \frac{Γ (1 - r + k) Γ (z)}{Γ (1 - r + k + z)}

we have that

\begin{array}{l} z^{r} & = \frac{z}{Γ (1 - r)} \int_{0}^{1} {(1 - u)}^{z - 1} u^{- r} {(\frac{1}{u} \ln (\frac{1}{1 - u}))}^{- r} d u \\ = \frac{z}{Γ (1 - r)} \int_{0}^{1} {(1 - u)}^{z - 1} u^{- r} \sum_{k} \{\binom{r}{r - k}\} \frac{Γ (1 - r) u^{k}}{Γ (- r + k + 1)} d u \\ = \sum_{k} \{\binom{r}{r - k}\} \frac{z}{Γ (- r + k + 1)} \int_{0}^{1} {(1 - u)}^{z - 1} u^{k - r} d u \\ = \sum_{k} \{\binom{r}{r - k}\} \frac{z}{Γ (- r + k + 1)} \frac{Γ (1 - r + k) Γ (z)}{Γ (1 - r + k + z)} \\ = \sum_{k} \{\binom{r}{r - k}\} \frac{z Γ (z)}{Γ (1 - r + k + z)} \\ = \sum_{k} \{\binom{r}{r - k}\} \frac{Γ (z + 1)}{Γ (z - r + k + 1)} \\ = \sum_{k} \{\binom{r}{r - k}\} \frac{z!}{(z - r + k)!} \\ = \sum_{k} \{\binom{r}{r - k}\} z^{\underset{̲}{r - k}} \end{array}

which establishes the case $Re (r) < 1$ . Then, assuming

z^{r} = \sum_{k} \{\binom{r}{r - k}\} z^{\underset{̲}{r - k}}

we must show that

z^{r + 1} = \sum_{k} \{\binom{r + 1}{r + 1 - k}\} z^{\underset{̲}{r + 1 - k}} .

But from the recurrence relations for falling factorial powers

z z^{\underset{̲}{r - k}} = z^{\underset{̲}{r - k + 1}} + (r - k) z^{\underset{̲}{r - k}}

and Eq. (46) we have that

\begin{array}{l} z^{r + 1} & = z z^{r} \\ = z \sum_{k} \{\binom{r}{r - k}\} z^{\underset{̲}{r - k}} \\ = \sum_{k} \{\binom{r}{r - k}\} z z^{\underset{̲}{r - k}} \\ = \sum_{k} \{\binom{r}{r - k}\} (z^{\underset{̲}{r - k + 1}} + (r - k) z^{\underset{̲}{r - k}}) \\ = \sum_{k} \{\binom{r}{r - k}\} z^{\underset{̲}{r - k + 1}} + \sum_{k - 1} \{\binom{r}{r - (k - 1)}\} (r - (k - 1)) z^{\underset{̲}{r - (k - 1)}} \\ = \sum_{k} \{\binom{r}{r - k}\} z^{\underset{̲}{r - k + 1}} + \sum_{k} \{\binom{r}{r - k + 1}\} (r - k + 1) z^{\underset{̲}{r - k + 1}} \\ = \sum_{k} (\{\binom{r}{r - k}\} + (r - k + 1) \{\binom{r}{r - k + 1}\}) z^{\underset{̲}{r - k + 1}} \\ = \sum_{k} \{\binom{r + 1}{r + 1 - k}\} z^{\underset{̲}{r + 1 - k}} \end{array}

as we needed to show. □

We may also prove Eq. (60).

Proposition. $z^{\underset{̲}{r}} = \sum_{0 \leq k \leq m} [\binom{r}{r - k}] {(- 1)}^{k} z^{r - k} + O (z^{r - m - 1})$ .

Proof. Let $r, z$ be arbitrary complex numbers. We must show that

z^{\underset{̲}{r}} = \sum_{0 \leq k \leq m} [\binom{r}{r - k}] {(- 1)}^{k} z^{r - k} + O (z^{r - m - 1}) .

By Euler-Maclaurin summation for Stirling’s approximation² we have that

\begin{array}{l} \begin{aligned} \sum_{1 \leq k < z} \ln (k) & = z \ln (z) - z + σ - \frac{\ln (z)}{2} \\ + \sum_{1 \leq k \leq m} \frac{B_{2 k}}{2 k (2 k - 1) z^{2 k - 1}} \\ + φ_{m, z} \frac{B_{2 m + 2}}{(2 m + 2) (2 m + 1) z^{2 m + 1}}, \end{aligned} \\ \begin{aligned} \sum_{1 \leq k < z - r} \ln (k) & = (z - r) \ln (z - r) - (z - r) + σ - \frac{\ln (z - r)}{2} \\ + \sum_{1 \leq k \leq m} \frac{B_{2 k}}{2 k (2 k - 1) {(z - r)}^{2 k - 1}} \\ + φ_{m, z - r} \frac{B_{2 m + 2}}{(2 m + 2) (2 m + 1) {(z - r)}^{2 m + 1}} \end{aligned} \end{array}

for an arbitrary positive integer $m$ , constant $σ$ , “Stirling’s constant,” Bernoulli numbers $B_{k}$ , and $0 < φ_{m, x} < 1$ , so that

\begin{array}{l} \ln \frac{z^{\underset{̲}{r}}}{z^{r}} \\ = \ln \frac{z!}{z^{r} (z - r)!} \\ = \ln (z!) - \ln ((z - r)!) - r \ln (z) \\ = - r \ln (z) + \sum_{1 \leq k \leq z} \ln (k) - \sum_{1 \leq k \leq z - r} \ln (k) \\ = - r \ln (z) + \ln (z) - \ln (z - r) + \sum_{1 \leq k < z} \ln (k) - \sum_{1 \leq k < z - r} \ln (k) \\ = (1 - r) \ln (z) - \ln (z - r) + \sum_{1 \leq k < z} \ln (k) - \sum_{1 \leq k < z - r} \ln (k) \\ \begin{aligned} = (1 - r) \ln (z) - \ln (z - r) \\ + z \ln (z) - z + σ - \frac{\ln (z)}{2} \\ + \sum_{1 \leq k \leq m} \frac{B_{2 k}}{2 k (2 k - 1) z^{2 k - 1}} \\ + φ_{m, z} \frac{B_{2 m + 2}}{(2 m + 2) (2 m + 1) z^{2 m + 1}} \\ - (z - r) \ln (z - r) + (z - r) - σ + \frac{\ln (z - r)}{2} \\ - \sum_{1 \leq k \leq m} \frac{B_{2 k}}{2 k (2 k - 1) {(z - r)}^{2 k - 1}} \\ - φ_{m, z - r} \frac{B_{2 m + 2}}{(2 m + 2) (2 m + 1) {(z - r)}^{2 m + 1}} \end{aligned} \\ \begin{aligned} = - r + (z - r + 1 ∕ 2) \ln (z) - (z - r + 1 ∕ 2) \ln (z - r) \\ + \sum_{1 \leq k \leq m} \frac{B_{2 k}}{2 k (2 k - 1)} (z^{- (2 k - 1)} - {(z - r)}^{- (2 k - 1)}) \\ + \frac{B_{2 m + 2}}{(2 m + 2) (2 m + 1)} (φ_{m, z} z^{- (2 m + 1)} - φ_{m, z - r} {(z - r)}^{- (2 m + 1)}) \end{aligned} \\ \begin{aligned} = - r - (z - r + 1 ∕ 2) \ln (1 - r ∕ z) \\ + \sum_{1 \leq k \leq m} \frac{B_{2 k}}{2 k (2 k - 1)} (z^{- (2 k - 1)} - {(z - r)}^{- (2 k - 1)}) \\ + \frac{B_{2 m + 2}}{(2 m + 2) (2 m + 1)} (φ_{m, z} z^{- (2 m + 1)} - φ_{m, z - r} {(z - r)}^{- (2 m + 1)}) . \end{aligned} \end{array}

That is, so that $\ln \frac{z^{\underset{̲}{r}}}{z^{r}}$ is a series in which each coeﬃcient of $z^{- k}$ is a polynomial in $r$ ; and so similarly for the exponential

\frac{z^{\underset{̲}{r}}}{z^{r}} = \sum_{0 \leq k \leq m} c_{k} (r) z^{- k} + O (z^{- m - 1})

with coeﬃcients $c_{k} (r)$ , polynomials in $r$ , and with asymptotic bounds $O (z^{- m - 1})$ , if and only if

z^{\underset{̲}{r}} = \sum_{0 \leq k \leq m} c_{k} (r) z^{r - k} + O (z^{r - m - 1}) .

From Eq. (44) for $r$ restricted to the integers

z^{\underset{̲}{r}} = \sum_{0 \leq k \leq r} [\binom{r}{k}] {(- 1)}^{r - k} z^{k} = \sum_{0 \leq k \leq r} [\binom{r}{r - k}] {(- 1)}^{k} z^{r - k},

and since $[\binom{r}{r - k}]$ is a polynomial in $r$ of degree $2 k$ whenever $k$ is a nonnegative integer, the coeﬃcients of $z^{r - k}$ hold for arbitrary complex $r$ such that

c_{k} (r) = [\binom{r}{r - k}] {(- 1)}^{k} .

Therefore

\begin{array}{l} \sum_{0 \leq k \leq m} c_{k} (r) z^{r - k} + O (z^{r - m - 1}) \\ = \sum_{0 \leq k \leq m} [\binom{r}{r - k}] {(- 1)}^{k} z^{r - k} + O (z^{r - m - 1}) . \end{array}

and hence the result

z^{\underset{̲}{r}} = \sum_{0 \leq k \leq m} [\binom{r}{r - k}] {(- 1)}^{k} z^{r - k} + O (z^{r - m - 1}) .

□

______________________________________________________________________________________________________________________________

AMM 99 (1992), 410–422.

Proposition. $(\binom{x}{n - 1}) \leq (\binom{y}{n - 1}) + (\binom{z}{n - 2})$ iﬀ $y \geq z$ , $(\binom{x}{n + 1}) \leq (\binom{y}{n + 1}) + (\binom{z}{n})$ iﬀ $y \leq z$ .

Proof. Let $x$ , $y$ , and $z$ be arbitrary real numbers and $n$ an arbitrary integer $\geq 2$ such that

(\binom{x}{n}) = (\binom{y}{n}) + (\binom{z}{n - 1}),

$x \geq n - 1$ , $y \geq n - 1$ , and $z > n - 2$ . We must show that both

(\binom{x}{n - 1}) \leq (\binom{y}{n - 1}) + (\binom{z}{n - 2}) \Leftrightarrow y \geq z

and

(\binom{x}{n + 1}) \leq (\binom{y}{n + 1}) + (\binom{z}{n}) \Leftrightarrow y \leq z .

We will ﬁrst show the former. Since $y \geq z$ ,

\begin{array}{l} (\binom{x}{n}) & = (\binom{y}{n}) + (\binom{z}{n - 1}) \\ \geq (\binom{z}{n}) + (\binom{z}{n - 1}) \\ \geq (\binom{z + 1}{n}), \end{array}

and so $x \geq z + 1$ . Given the identities

\begin{array}{l} (\binom{a + n - 1}{n - 1}) & = (\binom{a + 0 - (- 1) (n - 1)}{n - 1}) \\ = \sum_{0 \leq j \leq n - 1} (\binom{a - (- 1) j}{j}) (\binom{0 - (- 1) ((n - 1) - j)}{(n - 1) - j}) \frac{a}{a - (- 1) j} & from Eq. (26) \\ = \sum_{0 \leq j \leq n - 1} (\binom{a + j}{j}) (\binom{n - 1 - j}{n - 1 - j}) \frac{a}{a + j} \\ = \sum_{0 \leq j \leq n - 1} (\binom{a + j}{j}) \frac{a}{a + j} \\ = \sum_{0 \leq j \leq n - 1} \frac{(a + j)!}{j! (a + j - j)!} \frac{a}{a + j} \\ = \sum_{0 \leq j \leq n - 1} \frac{a (a + j)!}{(a + j) j! a!} \\ = \sum_{0 \leq j \leq n - 1} \frac{(a + j - 1)!}{j! (a + j - 1 - j)!} \\ = \sum_{0 \leq j \leq n - 1} (\binom{a + j - 1}{j}) \end{array}

and

\begin{array}{l} (\binom{a + b}{n}) & = (\binom{a + (b - n) - (- 1) n}{n}) \\ = \sum_{0 \leq j \leq n} (\binom{a - (- 1) j}{j}) (\binom{(b - n) - (- 1) (n - j)}{n - j}) \frac{a}{a - (- 1) j} & from Eq. (26) \\ = \sum_{0 \leq j \leq n} (\binom{a + j}{j}) (\binom{b - j}{n - j}) \frac{a}{a + j} \\ = \sum_{0 \leq j \leq n} \frac{a + j - j}{a + j} (\binom{a + j}{j}) (\binom{b - j}{n - j}) \\ = \sum_{0 \leq j \leq n} (\binom{a + j - 1}{j}) (\binom{b - j}{n - j}) & from Eq. (8) \end{array}

for arbitrary integers $a, b$ ; and letting $x = t + x^{'}$ , $y = t + y^{'}$ , $z = t + n - 1$ ,

\begin{array}{l} (\binom{x}{n}) = (\binom{t + x^{'}}{n}) & = \sum_{0 \leq j \leq n} (\binom{t + j - 1}{j}) (\binom{x^{'} - j}{n - j}), \\ (\binom{y}{n}) = (\binom{t + y^{'}}{n}) & = \sum_{0 \leq j \leq n} (\binom{t + j - 1}{j}) (\binom{y^{'} - j}{n - j}), \\ (\binom{z}{n - 1}) = (\binom{t + n - 1}{n - 1}) & = \sum_{0 \leq j \leq n - 1} (\binom{t + j - 1}{j}); \end{array}

we have that

\begin{array}{l} 0 & = (\binom{y}{n}) + (\binom{z}{n - 1}) - (\binom{x}{n}) \\ = \sum_{0 \leq j \leq n} (\binom{t + j - 1}{j}) (\binom{y^{'} - j}{n - j}) + \sum_{0 \leq j \leq n - 1} (\binom{t + j - 1}{j}) - \sum_{0 \leq j \leq n} (\binom{t + j - 1}{j}) (\binom{x^{'} - j}{n - j}) \\ \begin{aligned} = (\binom{t + n - 1}{n}) (\binom{y^{'} - n}{n - n}) - (\binom{t + n - 1}{n}) (\binom{x^{'} - n}{n - n}) \\ + \sum_{0 \leq j \leq n - 1} (\binom{t + j - 1}{j}) ((\binom{y^{'} - j}{n - j}) + 1 - (\binom{x^{'} - j}{n - j})) \end{aligned} \\ = (\binom{t + n - 1}{n}) - (\binom{t + n - 1}{n}) + \sum_{0 \leq j \leq n - 1} (\binom{t + j - 1}{j}) ((\binom{y^{'} - j}{n - j}) + 1 - (\binom{x^{'} - j}{n - j})) \\ = \sum_{0 \leq j \leq n - 1} (\binom{t + j - 1}{j}) φ_{n - j} \end{array}

where

φ_{i} = (\binom{y^{'} - n + i}{i}) + 1 - (\binom{x^{'} - n + i}{i}) .

Similarly, since $t$ increases by one as $n$ decreases by one,

\begin{array}{l} (\binom{y}{n - 1}) + (\binom{z}{n - 2}) - (\binom{x}{n - 1}) \\ = \sum_{0 \leq j \leq n - 2} (\binom{t + 1 + j - 1}{j}) φ_{n - 1 - j} \\ = \sum_{1 \leq j \leq n - 1} (\binom{t + j - 1}{j - 1}) φ_{n - j} \\ = \sum_{1 \leq j \leq n - 1} (\binom{t + j - 1}{j - 1}) φ_{n - j} \\ = \sum_{1 \leq j \leq n - 1} \frac{j}{t + j - 1 - j + 1} (\binom{t + j - 1}{j}) φ_{n - j} & from Eqs. (7), (8) \\ = \sum_{1 \leq j \leq n - 1} \frac{j}{t} (\binom{t + j - 1}{j}) φ_{n - j} \\ = \sum_{0 \leq j \leq n - 1} \frac{j}{t} (\binom{t + j - 1}{j}) φ_{n - j} \end{array}

with the understanding that in the case $t = 0$ , we deﬁne $\frac{0}{t} = 0$ . Then, for all $i$ , $1 \leq i \leq n - 1$ , since $x \geq y \Leftrightarrow x^{'} \geq y^{'}$ by hypothesis and $x^{'} = x - t \geq y - t \geq z + 1 - t = n$ ,

\begin{array}{l} φ_{i - 1} & = (\binom{y^{'} - n + i - 1}{i - 1}) + 1 - (\binom{x^{'} - n + i - 1}{i - 1}) \\ = \frac{i}{y^{'} - n + i} (\binom{y^{'} - n + i}{i}) + 1 - \frac{i}{x^{'} - n + i} (\binom{x^{'} - n + i}{i}) \\ \geq \frac{i}{x^{'} - n + i} (\binom{y^{'} - n + i}{i}) + \frac{i}{x^{'} - n + i} - \frac{i}{x^{'} - n + i} (\binom{x^{'} - n + i}{i}) \\ = \frac{i}{x^{'} - n + i} ((\binom{y^{'} - n + i}{i}) + 1 - (\binom{x^{'} - n + i}{i})) \\ = \frac{i}{x^{'} - n + i} φ_{i} \\ \geq 0 . \end{array}

but

\begin{array}{l} φ_{n} & = (\binom{y^{'} - n + n}{n}) + 1 - (\binom{x^{'} - n + n}{n}) \\ = (\binom{y^{'}}{n}) + 1 - (\binom{x^{'}}{n}) \\ = (\binom{y^{'}}{n}) + (\binom{n - 1}{n - 1}) - (\binom{x^{'}}{n}) \\ = (\binom{y - t}{n}) + (\binom{z - t}{n - 1}) - (\binom{x - t}{n}) \\ \leq 0 . \end{array}

And so ﬁnally,

\begin{array}{l} (\binom{y}{n - 1}) + (\binom{z}{n - 2}) - (\binom{x}{n - 1}) \\ = \sum_{0 \leq j \leq n - 1} \frac{j}{t} (\binom{t + j - 1}{j}) φ_{n - j} \\ \geq \sum_{0 \leq j \leq n - 1} \frac{1}{t} (\binom{t + j - 1}{j}) φ_{n - j} \\ = \frac{1}{t} \sum_{0 \leq j \leq n - 1} (\binom{t + j - 1}{j}) φ_{n - j} \\ = 0 \end{array}

and hence the former result.

We will then show the latter, and it is suﬃcient to show that if

(\binom{x}{n + 1}) - (\binom{y}{n + 1}) - (\binom{z}{n}) = 0

implies

\frac{d}{d z} ((\binom{x}{n + 1}) - (\binom{y}{n + 1}) - (\binom{z}{n})) \leq 0,

then

(\binom{x}{n + 1}) \leq (\binom{y}{n + 1}) + (\binom{z}{n}) \Leftrightarrow y \leq z .

But assuming

\begin{array}{l} (\binom{x}{n + 1}) - (\binom{y}{n + 1}) - (\binom{z}{n}) \\ = \frac{x - n}{n + 1} (\binom{x}{n}) - \frac{y - n}{n + 1} (\binom{y}{n}) - \frac{z - (n - 1)}{n} (\binom{z}{n - 1}) \\ = \frac{x - n}{n + 1} ((\binom{y}{n}) + (\binom{z}{n - 1})) - \frac{y - n}{n + 1} (\binom{y}{n}) - \frac{z - n + 1}{n} (\binom{z}{n - 1}) \\ = \frac{x - n}{n + 1} (\binom{y}{n}) + \frac{x - n}{n + 1} (\binom{z}{n - 1}) - \frac{y - n}{n + 1} (\binom{y}{n}) - \frac{z - n + 1}{n} (\binom{z}{n - 1}) \\ = \frac{x - n}{n + 1} (\binom{z}{n - 1}) + \frac{x - y}{n + 1} (\binom{y}{n}) - \frac{z - n + 1}{n} (\binom{z}{n - 1}) \\ = 0 \end{array}

and since $x \geq y \Leftrightarrow x - y \geq 0$ by hypothesis, we have that

\begin{array}{l} \frac{x - n}{n + 1} (\binom{z}{n - 1}) + \frac{x - y}{n + 1} (\binom{y}{n}) - \frac{z - n + 1}{n} (\binom{z}{n - 1}) = 0 \\ \Leftrightarrow \frac{x - n}{n + 1} (\binom{z}{n - 1}) - \frac{z - n + 1}{n} (\binom{z}{n - 1}) \leq 0 \\ \Leftrightarrow \frac{x - n}{n + 1} (\binom{z}{n - 1}) \leq \frac{z - n + 1}{n} (\binom{z}{n - 1}) \\ \Leftrightarrow \frac{x - n}{n + 1} \leq \frac{z - n + 1}{n} . \end{array}

Also, with $\frac{d}{d z} (\binom{z}{n - 1}) = \frac{d}{d z} (\binom{x}{n})$ , and given that $\frac{d}{d n} n! = \frac{d}{d n} Γ (n + 1) = n! (- γ + \sum_{1 \leq k \leq n} \frac{1}{k})$ for the Euler-Mascheroni constant $γ$ ,

\begin{array}{l} \frac{d}{d x} (\binom{x}{n}) / (\binom{x}{n}) \\ = \frac{1}{n!} \frac{d}{d x} \frac{x!}{(x - n)!} / \frac{x!}{n! (x - n)!} \\ = \frac{1}{n!} \frac{(x - n)! \frac{d}{d x} x! - x! \frac{d}{d x} (x - n)!}{{((x - n)!)}^{2}} / \frac{x!}{n! (x - n)!} \\ = \frac{(x - n)! \frac{d}{d x} x! - x! \frac{d}{d x} (x - n)!}{x! (x - n)!} \\ = \frac{(x - n)! x! (- γ + \sum_{1 \leq k \leq x} \frac{1}{k}) - x! (x - n)! (- γ + \sum_{1 \leq k \leq x - n} \frac{1}{k})}{x! (x - n)!} \\ = - γ + \sum_{1 \leq k \leq x} \frac{1}{k} + γ - \sum_{1 \leq k \leq x - n} \frac{1}{k} \\ = \sum_{x - n + 1 \leq k \leq x} \frac{1}{k} \\ = \sum_{0 \leq k \leq n - 1} \frac{1}{x - k} \end{array}

and

\begin{array}{l} \frac{n}{n + 1} \frac{d}{d z} (\binom{z}{n - 1}) / (\binom{z}{n - 1}) \\ = \frac{n}{(n + 1) (n - 1)!} \frac{d}{d z} \frac{z!}{(z - (n - 1))!} / \frac{z!}{(n - 1)! (z - (n - 1))!} \\ = \frac{n}{(n + 1) (n - 1)!} \frac{(z - (n - 1))! \frac{d}{d z} z! - z! \frac{d}{d z} (z - (n - 1))!}{{((z - (n - 1))!)}^{2}} / \frac{z!}{(n - 1)! (z - (n - 1))!} \\ = \frac{n}{n + 1} \frac{(z - (n - 1))! \frac{d}{d z} z! - z! \frac{d}{d z} (z - (n - 1))!}{z! (z - (n - 1))!} \\ = \frac{n}{n + 1} \frac{(z - (n - 1))! z! (- γ + \sum_{1 \leq k \leq z} \frac{1}{k}) - z! (z - (n - 1))! (- γ + \sum_{1 \leq k \leq z - (n - 1)} \frac{1}{k})}{z! (z - (n - 1))!} \\ = \frac{n}{n + 1} (- γ + \sum_{1 \leq k \leq z} \frac{1}{k} + γ - \sum_{1 \leq k \leq z - (n - 1)} \frac{1}{k}) \\ = \frac{n}{n + 1} \sum_{z - (n - 1) + 1 \leq k \leq z} \frac{1}{k} \\ = \frac{n}{n + 1} \sum_{0 \leq k \leq n - 2} \frac{1}{z - k} . \end{array}

Also, since

\begin{array}{l} \Leftrightarrow 1 = 1 \\ \Leftrightarrow \frac{d}{d x} (\binom{x}{n}) / \frac{d}{d x} (\binom{x}{n}) = \frac{d}{d z} (\binom{z}{n - 1}) / \frac{d}{d z} (\binom{z}{n - 1}) \\ \Leftrightarrow \frac{d}{d x} (\binom{x}{n}) \frac{d}{d z} (\binom{z}{n - 1}) / \frac{d}{d x} (\binom{x}{n}) = \frac{d}{d z} (\binom{z}{n - 1}) \\ \Leftrightarrow \frac{d}{d x} (\binom{x}{n}) \frac{d x}{d z} = \frac{d}{d z} (\binom{z}{n - 1}) \end{array}

and since for arbitrary integers $k \geq 0$ , $n \leq n + 1 \Rightarrow \frac{k}{n + 1} \leq \frac{k}{n}$ , we have that

\begin{array}{l} \frac{x - n}{n + 1} \leq \frac{z - n + 1}{n} \land \frac{k}{n + 1} \leq \frac{k}{n} \\ \Rightarrow \frac{x - n + k}{n + 1} + \frac{k}{n + 1} \leq \frac{z - n + 1}{n} + \frac{k}{n} . \\ \Leftrightarrow \frac{x - n + k}{n + 1} \leq \frac{z - n + 1 + k}{n} \\ \Leftrightarrow \frac{1}{x - n + k} \geq \frac{n}{n + 1} \frac{1}{z - n + 1 + k} \\ \Rightarrow \sum_{0 \leq k \leq n - 1} \frac{1}{x - k} \geq \frac{n}{n + 1} \sum_{0 \leq k \leq n - 1} \frac{1}{z - k} \\ \Rightarrow \sum_{0 \leq k \leq n - 1} \frac{1}{x - k} \geq \frac{n}{n + 1} \sum_{0 \leq k \leq n - 2} \frac{1}{z - k} \\ \Rightarrow \frac{d}{d x} (\binom{x}{n}) / (\binom{x}{n}) \geq \frac{n}{n + 1} \frac{d}{d z} (\binom{z}{n - 1}) / (\binom{z}{n - 1}) \\ \Leftrightarrow (\binom{z}{n - 1}) \geq \frac{n}{n + 1} (\binom{x}{n}) \frac{d}{d z} (\binom{z}{n - 1}) / \frac{d}{d x} (\binom{x}{n}) \\ \Leftrightarrow (\binom{z}{n - 1}) \geq \frac{n}{n + 1} (\binom{x}{n}) \frac{d x}{d z} \\ \Leftrightarrow \frac{1}{n} (\binom{z}{n - 1}) \geq \frac{1}{n + 1} (\binom{x}{n}) \frac{d x}{d z} \\ \Leftrightarrow \frac{1}{n + 1} (\binom{x}{n}) \frac{d x}{d z} \leq \frac{1}{n} (\binom{z}{n - 1}) \\ \Leftrightarrow \frac{1}{n + 1} (\binom{x}{n}) \frac{d x}{d z} - \frac{1}{n} (\binom{z}{n - 1}) \leq 0 . \end{array}

Then

\begin{array}{l} \frac{d}{d z} ((\binom{x}{n + 1}) - (\binom{y}{n + 1}) - (\binom{z}{n})) \\ = \frac{d}{d z} (\frac{x - n}{n + 1} (\binom{x}{n}) - \frac{y - n}{n + 1} (\binom{y}{n}) - \frac{z - (n - 1)}{n} (\binom{z}{n - 1})) \\ = \frac{d}{d z} \frac{x - n}{n + 1} (\binom{x}{n}) - \frac{d}{d z} \frac{y - n}{n + 1} (\binom{y}{n}) - \frac{d}{d z} \frac{z - (n - 1)}{n} (\binom{z}{n - 1}) \\ = \frac{d}{d x} \frac{d x}{d z} \frac{x - n}{n + 1} (\binom{x}{n}) - \frac{d}{d z} \frac{z - (n - 1)}{n} (\binom{z}{n - 1}) \\ = \frac{x - n}{n + 1} \frac{d}{d x} (\binom{x}{n}) \frac{d x}{d z} + \frac{1}{n + 1} (\binom{x}{n}) \frac{d x}{d z} - \frac{z - (n - 1)}{n} \frac{d}{d z} (\binom{z}{n - 1}) - \frac{1}{n} (\binom{z}{n - 1}) \\ = \frac{x - n}{n + 1} \frac{d}{d z} (\binom{z}{n - 1}) + \frac{1}{n + 1} (\binom{x}{n}) \frac{d x}{d z} - \frac{z - (n - 1)}{n} \frac{d}{d z} (\binom{z}{n - 1}) - \frac{1}{n} (\binom{z}{n - 1}) \\ = \frac{1}{n + 1} (\binom{x}{n}) \frac{d x}{d z} - \frac{1}{n} (\binom{z}{n - 1}) + (\frac{x - n}{n + 1} - \frac{z - n + 1}{n}) \frac{d}{d z} (\binom{z}{n - 1}) \\ \leq (\frac{x - n}{n + 1} - \frac{z - n + 1}{n}) \frac{d}{d z} (\binom{z}{n - 1}) \\ \leq 0 \end{array}

and hence the latter result. □

______________________________________________________________________________________________________________________________

L. Lovász, Combinatorial Problems and Exercises (1993), Problem 13.31(a); R. M. Redheﬀer, AMM 103 (1996), 62–64.

Proposition. $(\binom{n}{k}) \leq {(\frac{n e}{k})}^{k}$ .

Proof. Let $n$ and $k$ be arbitrary integers such that $n \geq k \geq 0$ . We must show that

(\binom{n}{k}) \leq {(\frac{n e}{k})}^{k} .

In the case that $k = 0$ , if we adopt the convention that ${(\frac{n e}{k})}^{0} = 1$ , then

(\binom{n}{0}) = 1 \leq {(\frac{n e}{k})}^{0} .

Otherwise, since clearly

n^{\underset{̲}{k}} \leq n^{k}

and from exercise 1.2.5-24

\frac{k^{k}}{e^{k - 1}} \leq k! iﬀ \frac{1}{k!} \leq \frac{e^{k - 1}}{k^{k}},

we have that

\begin{array}{l} (\binom{n}{k}) & = \frac{n^{\underset{̲}{k}}}{k!} \\ \leq \frac{n^{k}}{k!} \\ \leq \frac{e^{k - 1}}{k^{k}} n^{k} \\ = \frac{1}{e} \frac{n^{k} e^{k}}{k^{k}} \\ = \frac{1}{e} {(\frac{n e}{k})}^{k} \\ \leq {(\frac{n e}{k})}^{k} . \end{array}

Hence

(\binom{n}{k}) \leq {(\frac{n e}{k})}^{k}

for all integers $n \geq k \geq 0$ as we needed to show. □

Proposition. $\sum_{k} (\binom{n}{k}) p^{k} {(1 - p)}^{n - k} | k - n p | = 2 ⌈ n p ⌉ (\binom{n}{⌈ n p ⌉}) p^{⌈ n p ⌉} {(1 - p)}^{n + 1 - ⌈ n p ⌉}$ .

Proof. Let $n$ be a nonnegative integer. We must show that

\sum_{k} (\binom{n}{k}) p^{k} {(1 - p)}^{n - k} | k - n p | = 2 ⌈ n p ⌉ (\binom{n}{⌈ n p ⌉}) p^{⌈ n p ⌉} {(1 - p)}^{n + 1 - ⌈ n p ⌉} .

But

\begin{array}{l} \sum_{k} (\binom{n}{k}) p^{k} {(1 - p)}^{n - k} | k - n p | \\ \begin{aligned} = \sum_{k < ⌈ n p ⌉} (\binom{n}{k}) p^{k} {(1 - p)}^{n - k} | k - n p | \\ + \sum_{⌈ n p ⌉ \leq k} (\binom{n}{k}) p^{k} {(1 - p)}^{n - k} | k - n p | \end{aligned} \\ \begin{aligned} = \sum_{k < ⌈ n p ⌉} (\binom{n}{k}) p^{k} {(1 - p)}^{n - k} (n p - k) \\ + \sum_{⌈ n p ⌉ \leq k} (\binom{n}{k}) p^{k} {(1 - p)}^{n - k} (k - n p) \end{aligned} \\ \begin{aligned} = \sum_{k < ⌈ n p ⌉} (\binom{n}{k}) p^{k} {(1 - p)}^{n - k} ((k + 1) \frac{n - k}{k + 1} p - k (1 - p)) \\ + \sum_{⌈ n p ⌉ \leq k} (\binom{n}{k}) p^{k} {(1 - p)}^{n - k} (k (1 - p) - (k + 1) \frac{n - k}{k + 1} p) \end{aligned} \\ \begin{aligned} = \sum_{k < ⌈ n p ⌉} ((k + 1) (\binom{n}{k + 1}) p^{k + 1} {(1 - p)}^{n + 1 - (k + 1)} - k (\binom{n}{k}) p^{k} {(1 - p)}^{n + 1 - k}) \\ + \sum_{⌈ n p ⌉ \leq k} (k (\binom{n}{k}) p^{k} {(1 - p)}^{n + 1 - k} - (k + 1) (\binom{n}{k + 1}) p^{k + 1} {(1 - p)}^{n + 1 - (k + 1)}) \end{aligned} \\ \begin{aligned} = ⌈ n p ⌉ (\binom{n}{⌈ n p ⌉}) p^{⌈ n p ⌉} {(1 - p)}^{n + 1 - ⌈ n p ⌉} \\ + ⌈ n p ⌉ (\binom{n}{⌈ n p ⌉}) p^{⌈ n p ⌉} {(1 - p)}^{n + 1 - ⌈ n p ⌉} \end{aligned} \\ = 2 ⌈ n p ⌉ (\binom{n}{⌈ n p ⌉}) p^{⌈ n p ⌉} {(1 - p)}^{n + 1 - ⌈ n p ⌉} \end{array}

as we needed to show. □

______________________________________________________________________________________________________________________________

De Moivre, Miscellanea Analytica (1730), 101; H. Poincaré, Calcul des Probabilités (1896), 56–60; P. Diaconis and S. Zabell, Statistical Science 6 (1991), 284–302.

$a$	$b$	$c$	$n$

2	1	0	0
3	1	0	1
3	2	0	2
3	2	1	3
4	1	0	4
4	2	0	5
4	2	1	6
4	3	0	7
4	3	1	8
4	3	2	9
5	1	0	10
5	2	0	11
5	2	1	12
5	3	0	13
5	3	1	14
5	3	2	15
5	4	0	16
5	4	1	17
5	4	2	18
5	4	3	19
6	1	0	20

$a$	$b$	$c$	$n$

2	1	0	0
3	1	0	1
3	2	0	2
3	2	1	3
4	1	0	4
4	2	0	5
4	2	1	6
4	3	0	7
4	3	1	8
4	3	2	9
5	1	0	10
5	2	0	11
5	2	1	12
5	3	0	13
5	3	1	14
5	3	2	15
5	4	0	16
5	4	1	17
5	4	2	18
5	4	3	19
6	1	0	20

$a$	$b$	$c$	$n$

2	1	0	0
3	1	0	1
3	2	0	2
3	2	1	3
4	1	0	4
4	2	0	5
4	2	1	6
4	3	0	7
4	3	1	8
4	3	2	9
5	1	0	10
5	2	0	11
5	2	1	12
5	3	0	13
5	3	1	14
5	3	2	15
5	4	0	16
5	4	1	17
5	4	2	18
5	4	3	19
6	1	0	20