TAOCP 1.2.6 Exercise 41

Define I(x,y)=\frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)}.

taocpmathematicsalgorithmsvolume-1hm-medium

Section 1.2.6: Binomial Coefficients

Exercise 41. [HM22] Prove that

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

Verified: no
Solve time: -

Solution

Define

$$ I(x,y)=\frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)}. $$

We will show that $I(x,y)$ satisfies the same defining relations as $B(x,y)$ in Exercise 40.

From the definition of the gamma function,

$$ \Gamma(x+1)=x\Gamma(x), \qquad x>0. $$

Hence

$$ I(x,1) = \frac{\Gamma(x)\Gamma(1)}{\Gamma(x+1)}. $$

Since

$$ \Gamma(1)=\int_0^\infty e^{-t},dt=1, $$

and since $\Gamma(x+1)=x\Gamma(x)$,

$$ I(x,1) = \frac{\Gamma(x)}{x\Gamma(x)} = \frac1x. $$

Similarly,

$$ I(1,x)=\frac1x. $$

Therefore $I(x,1)$ and $I(1,x)$ agree with part 1 of Exercise 40.

Next,

$$ I(x+1,y) = \frac{\Gamma(x+1)\Gamma(y)}{\Gamma(x+y+1)} = \frac{x\Gamma(x)\Gamma(y)}{(x+y)\Gamma(x+y)} = \frac{x}{x+y}I(x,y), $$

and similarly,

$$ I(x,y+1) = \frac{y}{x+y}I(x,y). $$

Adding,

$$ I(x+1,y)+I(x,y+1) = \frac{x+y}{x+y}I(x,y) = I(x,y). $$

This agrees with part 2 of Exercise 40.

Also,

$$ I(x,y+1) = \frac{y}{x+y}I(x,y), $$

therefore

$$ I(x,y) = \frac{x+y}{y}I(x,y+1), $$

which agrees with part 3 of Exercise 40.

Now define

$$ D(x,y)=B(x,y)-I(x,y). $$

The preceding calculations show that

$$ D(x,1)=D(1,x)=0, $$

and

$$ D(x+1,y)+D(x,y+1)=D(x,y). $$

We prove by induction on $n$ that

$$ D(x,n)=0 \qquad (n\ge1). $$

The case $n=1$ holds. Assume $D(x,n)=0$. Then

$$ 0 = D(x,n) = D(x+1,n-1)+D(x,n), $$

by the recurrence relation with $y=n-1$. Hence

$$ D(x+1,n-1)=0. $$

Replacing $x+1$ by $x$ gives

$$ D(x,n-1)=0. $$

Thus the induction proceeds downward from $n$ to $1$, and consequently

$$ D(x,n)=0 \qquad\text{for all integers }n\ge1. $$

Fix $y>0$. Both $B(x,y)$ and $I(x,y)$ satisfy

$$ F(x,y)=\frac{x+y}{y}F(x,y+1), $$

therefore repeated application gives

$$ F(x,y) = \frac{(x+y)(x+y+1)\cdots(x+y+n-1)} {y(y+1)\cdots(y+n-1)} F(x,y+n). $$

Applying this to $D$,

$$ D(x,y) = \frac{(x+y)^{\overline n}} {y^{\overline n}} D(x,y+n), $$

where

$$ a^{\overline n}=a(a+1)\cdots(a+n-1). $$

Since $y+n$ is eventually an integer $>0$, and since $D(x,m)=0$ for every positive integer $m$, we obtain

$$ D(x,y)=0. $$

Therefore

$$ B(x,y)=I(x,y) = \frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)}. $$

Hence

$$ \boxed{B(x,y)=\dfrac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)}}. $$

This completes the proof.

∎