TAOCP 4.5.3 Exercise 19

Exercise 19. [M20] Prove $F(x) = \log_2(1 + x)$ satisfies Eq. (24).

Verified: no
Solve time: 1m50s

Solution

Equation (24) is

$$ F(x)=\sum_{k\ge1}\left(F!\left(\frac1k\right)-F!\left(\frac1{k+x}\right)\right), \qquad 0\le x\le1. $$

Let

$$ F(x)=\log_2(1+x). $$

Then

$$ F!\left(\frac1k\right)-F!\left(\frac1{k+x}\right) = \log_2!\left(\frac{k+1}{k}\right) - \log_2!\left(\frac{k+x+1}{k+x}\right), $$

hence

$$ F!\left(\frac1k\right)-F!\left(\frac1{k+x}\right) = \log_2!\left( \frac{(k+1)(k+x)} {k(k+x+1)} \right). $$

Therefore the partial sums of the right-hand side of (24) are

$$ S_N = \sum_{k=1}^{N} \log_2!\left( \frac{(k+1)(k+x)} {k(k+x+1)} \right) = \log_2 \prod_{k=1}^{N} \frac{(k+1)(k+x)} {k(k+x+1)}. $$

The product factors into two telescoping products:

$$ \prod_{k=1}^{N}\frac{k+1}{k}=N+1, $$

and

$$ \prod_{k=1}^{N}\frac{k+x}{k+x+1} = \frac{1+x}{N+x+1}. $$

Hence

$$ S_N = \log_2!\left( (N+1)\frac{1+x}{N+x+1} \right). $$

Letting $N\to\infty$ gives

$$ \lim_{N\to\infty}S_N = \log_2!\left( (1+x)\lim_{N\to\infty}\frac{N+1}{N+x+1} \right) = \log_2(1+x). $$

Since $\log_2(1+x)=F(x)$, we obtain

$$ \sum_{k\ge1} \left( F!\left(\frac1k\right) - F!\left(\frac1{k+x}\right) \right) = F(x). $$

Thus $F(x)=\log_2(1+x)$ satisfies equation (24).

This completes the proof.

∎