# Factorial canceling on expansion of binomial coefficients on Concrete Mathematics

On Concrete Mathematics section 5.5, which is teaching the hypergeometric functions, generalized factorials is defined as:

$\frac 1 {z!} = \lim_{n \to \infty} \binom{n+z}{n}n^{-z}$

where

$\binom r k = \left\{ \begin{array}{ll} r^{\underline k} / k! = r(r-1) \cdots (r-k+1) / k! & k > 0 \\ 1 & k = 0 \\ 0 & k < 0 \end{array} \right.$

follows the ordinary definition.

So $z! = z(z-1)!$ for all complex $z$ (except negative integers), then we can check $0! = 1$ and $n! = n(n-1) \cdots 1$ for $n > 0$.

Then, a binomial coefficient can be written

$\binom z w = \lim_{\zeta \to z} \lim_{\omega \to w} \frac{\zeta!}{\omega!(\zeta-\omega)!}$

Let $t_k = \dbinom r k \dbinom s {n-k}$.

However, the succeeding paragraph says that

$t_k = \frac{r!}{(r-k)!k!} \frac{s!}{(s-n+k)!(n-k)!}$ and we are no longer too shy to use generalized factorials in these expressions.

without limits (it is said that we must use appropriate limiting values when these formulas give $\infty / \infty$) and considers the ratio $t_{k+1} / t_k$ for all $t_k \neq 0$ and cancels some factorials using the property $z! = z(z-1)!$

I'm "too shy" and my question remains: why can we do such canceling?

To observe closely, we take a variety of an example from section 5.7:

Considering indefinite summation $\sum \binom n {-k} \delta k, \qquad n < 0$

Let $t(k) = \dbinom n {-k} = \dfrac{n!}{(-k)!(n+k)!}$, we have $\frac{t(k+1)}{t(k)} = \frac{n!}{(-k-1)!(n+k+1)!} \frac{(-k)!(n+k)!}{n!} = -\frac{k}{n+k+1}$

Let $n = -1$, we have $t(k+1) / t(k) = -1$ for $t(k) \neq 0$. But it's wrong for $k = 0$, where $t(1) = 0$ and $t(0) = 1$.

To see how the error happens, we resume the $\lim$ notation:

\begin{align*} t(k+1) &= \binom n {-k-1} \\ &= \lim_{z_2 \to 0} \lim_{z_1 \to 0} \frac{(n+z_2)!}{(-k-1+z_1)!(n+k+1-z_1+z_2)!} \\ &= \lim_{z_2 \to 0} \lim_{z_1 \to 0} \frac{-k+z_1}{n+k+1-z_1+z_2} \frac{(n+z_2)!}{(-k+z_1)!(n+k-z_1+z_2)!} \\ &= \binom n {-k} \lim_{z_2 \to 0} \lim_{z_1 \to 0} \frac{-k+z_1}{n+k+1-z_1+z_2} \end{align*} So when $n = -1$ and $k = 0$, we have $\lim_{z_2 \to 0} \lim_{z_1 \to 0} (-k+z_1)/(n+k+1-z_1+z_2) = 0$ not $-k/(n+k+1)$.

Another example (also from section 5.5) is:

$\lim_{x \to -1} \frac{x!}{(x-1)!} = \lim_{x \to -1} x = -1$ but $\lim_{x \to -1} \frac{x!}{(2x)!} = -2$ because of $(-z)! \Gamma(z) = \pi / \sin(z\pi)$, so expression $(-2)! / (-1)!$ is illegal.

My question is: in the frame of Concrete Mathematics, how to prevent such errors?

Thanks a lot.

• How is $\binom{n+z}{n}$ defined during the definition of $1/z!$ for complex $z$? – anon May 3 '12 at 9:40
• @anon Related to the normal definition for binomial coefficents. – Yai0Phah May 3 '12 at 13:52
• @anon I've added something. Fixed. – Yai0Phah May 3 '12 at 14:01

## 1 Answer

If the factorials in the limit expression differ by an integer, then cancel away.

But if the difference only becomes an integer in the limit, then you obviously cannot cancel before taking the limit, so you are not allowed to cancel at all.

The difference between $x$ and $2x$ is $x$ which is not an integer until the limit of $-1$ is reached.

• How to prevent from $\dbinom r k \neq \dbinom r {r-k}$ where $r$ is a negative integer. – Yai0Phah May 27 '12 at 3:29
• @FrankScience If the binomial coefficient is defined by a limit, you don't want to prevent that. The equality is only wrong if you say that binomial coefficients with negative value below is zero. But in the limit definition this is not true anymore. – Phira May 27 '12 at 9:02
• The limit definition is always true. When $k$ is a negative integer, $\displaystyle \binom r k = \lim_{u \to r} \lim_{v \to k} \frac {u!} {v!(u-v)!} = \lim_{u \to r} 0 = 0$. The book says that: I see, the lower index arrives at its limit first. That's why $\binom z w$ is zero when $w$ is a negative integer. The value is infinite when $z$ is a negative integer and $w$ is not an integer. – Yai0Phah May 27 '12 at 9:09