TAOCP 1.2.6 Exercise 40

1.

taocpmathematicsalgorithmsvolume-1hm-medium

Section 1.2.6: Binomial Coefficients

Exercise 40. [HM17] The beta function $B(x,y)$ is defined for positive real numbers $x,y$ by

$$ B(x,y) = \int_0^1 t^{x-1}(1-t)^{y-1},dt. $$

Show that:

  1. $B(x,1)=B(1,x)=1/x$.
  2. $B(x+1,y)+B(x,y+1)=B(x,y)$.
  3. $B(x,y)=((x+y)/y)B(x,y+1)$.

Verified: no
Solve time: -

Solution

  1. By definition,

$$ B(x,1) = \int_0^1 t^{x-1} (1-t)^{1-1}, dt = \int_0^1 t^{x-1}, dt. $$

Since $x>0$, the integral converges and evaluates to

$$ \int_0^1 t^{x-1}, dt = \left[ \frac{t^x}{x} \right]_0^1 = \frac{1}{x}. $$

Similarly,

$$ B(1,x) = \int_0^1 t^{1-1} (1-t)^{x-1}, dt = \int_0^1 (1-t)^{x-1}, dt. $$

With the substitution $u = 1-t$, $du = -dt$, $t=0 \mapsto u=1$, $t=1 \mapsto u=0$, we have

$$ B(1,x) = \int_1^0 u^{x-1}(-du) = \int_0^1 u^{x-1}, du = \frac{1}{x}. $$

Hence $B(x,1)=B(1,x)=1/x$.

  1. Consider

$$ B(x+1,y)+B(x,y+1) = \int_0^1 t^x (1-t)^{y-1}, dt + \int_0^1 t^{x-1} (1-t)^y, dt. $$

Combine the two integrals into a single integral:

$$ \int_0^1 \bigl[ t^x (1-t)^{y-1} + t^{x-1} (1-t)^y \bigr], dt. $$

Factor $t^{x-1} (1-t)^{y-1}$:

$$ t^{x-1} (1-t)^{y-1} \bigl[ t + (1-t) \bigr] = t^{x-1} (1-t)^{y-1}. $$

Thus

$$ B(x+1,y)+B(x,y+1) = \int_0^1 t^{x-1} (1-t)^{y-1}, dt = B(x,y). $$

  1. Start from the definition:

$$ B(x,y+1) = \int_0^1 t^{x-1} (1-t)^y, dt. $$

Factor $(1-t)$ from $(1-t)^{y} = (1-t)^{y-1} (1-t)$:

$$ B(x,y+1) = \int_0^1 t^{x-1} (1-t)^{y-1} (1-t), dt = \int_0^1 t^{x-1} (1-t)^{y-1}, dt - \int_0^1 t^{x-1} (1-t)^y, dt. $$

The first integral is $B(x,y)$ and the second is $B(x,y+1)$, hence

$$ B(x,y+1) = B(x,y) - B(x,y+1) \implies 2 B(x,y+1) = B(x,y) \quad \text{(incorrect: check factor)}. $$

Correctly, we solve

$$ B(x,y) - B(x,y+1) = \int_0^1 t^{x-1} (1-t)^{y-1} - t^{x-1} (1-t)^y , dt = \int_0^1 t^{x-1} (1-t)^{y-1} (1 - (1-t)), dt = \int_0^1 t^{x} (1-t)^{y-1}, dt = B(x+1,y). $$

Thus we obtain

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

Next, divide both sides by $B(x,y+1)$:

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

Use the substitution $t = u$, $dt = du$, and the identity

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

which is standard from the formula

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

Alternatively, use integration by parts on $B(x,y+1)$:

$$ B(x,y+1) = \int_0^1 t^{x-1} (1-t)^y, dt. $$

Let $u = (1-t)^y$, $dv = t^{x-1} dt$, then $du = -y(1-t)^{y-1} dt$, $v = t^x / x$. Integration by parts gives

$$ B(x,y+1) = \frac{1}{x} \Bigl[ t^x (1-t)^y \Big|_0^1 + y \int_0^1 t^x (1-t)^{y-1} dt \Bigr] = \frac{y}{x} B(x+1,y), $$

since the boundary terms vanish. Therefore

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

This completes the proof.

∎