# A finite sum involving the binomial coefficients and the harmonic numbers

Wikipedia has a proof of the identity $$H_{n} =\sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} \frac{1}{k}$$

http://en.wikipedia.org/wiki/Harmonic_number#Calculation

Curiously, there is also the identity

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

Can the second identity be derived from the first one?

This is a consequence of binomial inversion. In general, if $f_{n}$ and $g_{n}$ are sequences such that $$f_{n} = \sum_{k=0}^{n}g_{k}{n \choose k}$$

then

$$g_{n} = \sum_{k=0}^{n}(-1)^{n+k}f_{k}{n\choose k}$$

Here I take sequences to be functions from $\mathbb{N} \rightarrow \mathbb{R}$ where I am using the convention that the natural numbers start at $0$.

The second of your identities can be proved from the first using binomial inversion by taking $$f_n = \left\{ \begin{array}{lr} 0 & : n = 0\\ H_{n} & : n > 0 \end{array} \right.$$ and $$g_n = \left\{ \begin{array}{lr} 0 & : n = 0\\ (-1)^{n-1}\frac{1}{n} & : n > 0 \end{array} \right.$$

Several proofs of binomial inversion are given in the answer I linked to.

We have

$$(x+y)^n=\sum_{k=0}^n{n\choose k}x^{n-k}y^k$$

set $$x=1$$ and $$y=-t$$ we get

$$(1-t)^n=\sum_{k=0}^n{n\choose k}(-1)^k t^k=-1+\sum_{k=1}^n(-1)^k{n\choose k} t^k$$

Differentiate both sides with respect to $$t$$

$$-n(1-t)^{n-1}=\sum_{k=1}^n(-1)^k{n\choose k} k\ t^{k-1}$$

Now multiply both sides by $$\ln(1-t)$$ then $$\int_0^1 dt$$ and use the fact that $$\int_0^1 t^{k-1}\ln(1-t)\ dt=-\frac{H_k}{k}$$

$$\sum_{k=1}^n(-1)^{k-1}{n\choose k} H_k=-n\int_0^1 (1-t)^{n-1}\ln(1-t)\ dt$$ $$\overset{1-t\to t}{=}-n\int_0^1 t^{n-1}\ln(t)\ dt=-n\left(-\frac{1}{n^2}\right)=\frac1n$$

Bonus:

If we follow the same approach without differentiating we will have

$$\sum_{k=1}^n(-1)^{k-1}{n\choose k} \frac{H_k}{k}=H_n^{(2)}$$
