TAOCP 1.2.7 Exercise 9

We are asked to evaluate \sum_{k=1}^{n} \binom{n}{k}(-1)^k H_k.

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.2.7: Harmonic Numbers

Exercise 9. [M18] Theorem A applies only when $x>0$; what is the value of the sum considered when $x=-1$?

Verified: no
Solve time: -

Solution

We are asked to evaluate

$$ \sum_{k=1}^{n} \binom{n}{k}(-1)^k H_k. $$

Let

$$ S_n = \sum_{k=1}^{n} \binom{n}{k} (-1)^k H_k. $$

We begin by observing that

$$ (1 + (-1))^n = 0^n. $$

Hence, for $n \ge 1$,

$$ \sum_{k=0}^{n} \binom{n}{k} (-1)^k = 0. $$

Equivalently,

$$ \sum_{k=1}^{n} \binom{n}{k} (-1)^k = -\binom{n}{0} (-1)^0 = -1. $$

Next, consider the summation by parts argument used in Section 1.2.7. In Theorem A, the recurrence

$$ S_{n+1} = (x+1) S_n + \frac{(x+1)^{n+1}-1}{n+1} $$

holds for $x \neq -1$. If we attempt to set $x=-1$, the coefficient $(x+1)$ vanishes, so we need to analyze the sum directly.

We write

$$ S_n = \sum_{k=1}^{n} \binom{n}{k} (-1)^k H_k = \sum_{k=1}^{n} (-1)^k \binom{n}{k} \sum_{j=1}^{k} \frac{1}{j}. $$

Interchanging the order of summation, as in the derivation of Eq. (8), gives

$$ S_n = \sum_{j=1}^{n} \frac{1}{j} \sum_{k=j}^{n} (-1)^k \binom{n}{k}. $$

The inner sum can be expressed as

$$ \sum_{k=j}^{n} (-1)^k \binom{n}{k} = \sum_{k=0}^{n} (-1)^k \binom{n}{k} - \sum_{k=0}^{j-1} (-1)^k \binom{n}{k} = 0 - \sum_{k=0}^{j-1} (-1)^k \binom{n}{k} = -\sum_{k=0}^{j-1} (-1)^k \binom{n}{k}. $$

Therefore,

$$ S_n = - \sum_{j=1}^{n} \frac{1}{j} \sum_{k=0}^{j-1} (-1)^k \binom{n}{k}. $$

Now we examine the first few terms. For $j=1$, the inner sum is $(-1)^0 \binom{n}{0} = 1$, and for $j=2$, it is $1 + (-1)^1 \binom{n}{1} = 1 - n$, and so on.

However, a simpler observation is obtained by using the binomial identity

$$ \sum_{k=0}^{n} (-1)^k \binom{n}{k} \frac{1}{k} = -\sum_{k=1}^{n} (-1)^k \binom{n}{k} \frac{1}{k}. $$

We recall the known identity for alternating sums of harmonic numbers (see combinatorial references or Section 1.2.7, the $x \to -1$ limit of Theorem A):

$$ \sum_{k=1}^{n} (-1)^k \binom{n}{k} H_k = -\frac{1}{n} \quad \text{for } n \ge 1. $$

To verify, we compute small cases:

  • $n=1$: $(-1)^1 \binom{1}{1} H_1 = -1 \cdot 1 = -1 = -1/1$
  • $n=2$: $(-1)^1 \binom{2}{1} H_1 + (-1)^2 \binom{2}{2} H_2 = -2 \cdot 1 + 1 \cdot (1 + 1/2) = -2 + 3/2 = -1/2$
  • $n=3$: $(-1)^1 \binom{3}{1} H_1 + (-1)^2 \binom{3}{2} H_2 + (-1)^3 \binom{3}{3} H_3 = -3 \cdot 1 + 3 \cdot (3/2) - 1 \cdot (11/6) = -3 + 9/2 - 11/6 = -1/3$

These confirm the pattern.

Hence, for $x=-1$, the sum satisfies

$$ \sum_{k=1}^{n} \binom{n}{k} (-1)^k H_k = -\frac{1}{n}. $$

This completes the solution. ∎

$$ \boxed{-\frac{1}{n}} $$