TAOCP 1.2.6 Exercise 47

Exercise 47. [M21] Given that $k$ is an integer, show that

$$ \binom{r}{k}\binom{r-1/2}{k} = \binom{2r}{k}\binom{2r-k}{k}/4^k = \binom{2r}{2k}\binom{2k}{k}/4^k. $$

Give a simpler formula for the special case $r=-1/2$.

Verified: no
Solve time: -

Solution

Let $k$ be an integer. From the definition (3) of generalized binomial coefficients, we have

$$ \binom{r}{k} = \frac{r^{\underline{k}}}{k!}, \qquad \binom{r-1/2}{k} = \frac{(r-1/2)^{\underline{k}}}{k!}, $$

where $r^{\underline{k}} = r(r-1)\cdots(r-k+1)$ denotes the falling factorial. Then the left-hand side of the identity in the exercise is

$$ \binom{r}{k}\binom{r-1/2}{k} = \frac{r^{\underline{k}} (r-1/2)^{\underline{k}}}{(k!)^2}. $$

Next, consider the first expression on the right-hand side. We have

$$ \binom{2r}{k}\binom{2r-k}{k}/4^k = \frac{(2r)^{\underline{k}} , (2r-k)^{\underline{k}}}{(k!)^2 , 4^k}. $$

Observe that

$$ (2r)^{\underline{k}} = 2^k r^{\underline{k}} \prod_{j=0}^{k-1} (1 - \tfrac{j}{2r}) \quad \text{and} \quad (2r-k)^{\underline{k}} = 2^k (r - \tfrac{k}{2})^{\underline{k}} \prod_{j=0}^{k-1} (1 - \tfrac{j}{2r-k}), $$

but more systematically, we can factor each term as

$$ (2r)^{\underline{k}} (2r-k)^{\underline{k}} / 4^k = \prod_{j=0}^{k-1} \frac{(2r-j)(2r-k-j)}{4} = \prod_{j=0}^{k-1} \left(r - \frac{j}{2}\right)\left(r - \frac{k+j}{2}\right). $$

Reindexing the product and simplifying, we find

$$ \prod_{j=0}^{k-1} \left(r - j\right)\left(r - \frac{1}{2} - j\right) = r^{\underline{k}} (r-1/2)^{\underline{k}}. $$

Therefore, the first equality is verified:

$$ \binom{r}{k}\binom{r-1/2}{k} = \frac{\binom{2r}{k} \binom{2r-k}{k}}{4^k}. $$

To obtain the second form, note that

$$ \binom{2r}{2k}\binom{2k}{k}/4^k = \frac{(2r)^{\underline{2k}}}{(2k)!} \cdot \frac{(2k)^{\underline{k}}}{k!} \cdot \frac{1}{4^k} = \frac{(2r)^{\underline{2k}}}{(2k)!} \cdot \frac{k!}{k!} \cdot \frac{(2k)!}{k! , k!} \cdot \frac{1}{4^k} = \frac{(2r)^{\underline{2k}}}{(2k)!} \cdot \frac{(2k)!}{(k!)^2 , 4^k}. $$

Using the identity $(2r)^{\underline{2k}} / 4^k = r^{\underline{k}} (r-1/2)^{\underline{k}}$, we recover the previous expression. Hence

$$ \binom{r}{k}\binom{r-1/2}{k} = \frac{\binom{2r}{k} \binom{2r-k}{k}}{4^k} = \frac{\binom{2r}{2k} \binom{2k}{k}}{4^k}. $$

For the special case $r = -1/2$, we have

$$ \binom{-1/2}{k}\binom{-1}{k} = \binom{-1/2}{k}\cdot 0 = 0 \quad \text{for } k > 0, $$

since $\binom{-1}{k} = 0$ for $k > 0$ by definition (3). For $k=0$, both sides equal $1$. A simpler formula is therefore

$$ \binom{-1/2}{k}\binom{-1}{k} = \delta_{k,0}, $$

where $\delta_{k,0}$ denotes the Kronecker delta. Alternatively, using the middle expression, we have

$$ \frac{\binom{-1}{k} \binom{-1-k}{k}}{4^k} = \frac{0 \cdot \binom{-1-k}{k}}{4^k} = 0 \quad \text{for } k > 0, $$

and $1$ for $k=0$. This completes the identification of the simpler formula.

This completes the proof.

∎