Help with combinatorial proof of identity: $\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$ How to prove this identity? Can someone please give me some insight ?
$$\sum_{k=1}^{n}
\frac{(-1)^{k+1}}{k}
\binom{n}{k} =
\sum_{k=1}^{n}
\frac{1}{k}$$
 A: I don't know how to do it by a combinatorial proof, but here is an alternative:
$$\eqalign{RHS
  &=\sum_{k=1}^n\int_0^1x^{k-1}\,dx\cr
  &=\int_0^1 \frac{1-x^n}{1-x}\,dx\cr
  &=\int_0^1 \frac{1-(1-y)^n}{y}\,dy\cr
  &=\int_0^1 \sum_{k=1}^n\binom{n}{k}(-1)^{k+1}y^{k-1}\,dy\cr
  &=LHS\ .\cr}$$
I would be very interested to see if there is a true combinatorial proof: I would have thought the $1/k$ terms would make that rather difficult.
A: this is too long for a comment. it is already established that $ n! RHS = s(n+1, 2).$ we will show that $s(n+1, 2) - \frac{n!}{1} {n \choose 1} + \frac{n!}{2}{n \choose 2} + \ldots = 0$  as in @markus answer, let the elements of $s(n,2)$ written in left cycle with $1$ as the first element and the right cycle starts with smallest element of that cycle.
let $\alpha_j, j = 1, 2, \ldots$ be the property that $j+1$ is in the right cycle.
claim: $N(\alpha_j) = n!, N(\alpha_j \alpha_k) = \frac{n!}{2}, \ldots.$
place $1$ in the left cycle and $2$ in the right cycle as the first elements.
now, $3$ has two choices, $4$ has $2$ choices, $\ldots (n+1) \mbox{has} n$ choices. putting all together, $ N(\alpha_1) = n!.$
to prove the second claim, place $1,2$ as before and put $3$ to the right of $2.$ we can place $4$ in $3$ ways between $1$ and $2, 2$ and $3$ or to the right of $3,$ so there are $3$ ways. same way $5$ has $4$ choices giving us
$N(\alpha_j \alpha_k = \frac{n!}{2}.$
by symmetry, $N(\alpha_j), N(\alpha_j \alpha_k), \ldots$ don't depend on $j, k, \ldots.$
we are now ready to apply the principle of inclusion-inclusion in the form
$N[(1-\alpha_1)(1-\alpha_2)\ldots] = N(1) - {n \choose 1} N(\alpha_1) + {n \choose 2} N(\alpha_1 \alpha_2) + \ldots.$ this gives us
$$0 = s(n+1, 2) -  \frac{n!}{1} {n \choose 1} + \frac{n!}{2}{n \choose 2} + \ldots $$
