# Combinatorial proof involving reciprocals

This is a follow-up to this question: show that if $n$ is a positive integer then $$\sum_{k=1}^{n}\frac{(-1)^{k+1}}{k}\binom{n}{k} =\sum_{k=1}^{n}\frac{1}{k}\ .$$ I was able to answer the question by an argument involving definite integrals, but I would be interested to see a combinatorial proof. There is a proof here by induction, which however IMHO is not a true combinatorial proof as it does not rely on solving a counting problem in two ways.

In a comment on my answer, Jack D'Aurizio pointed to the problem of counting the number of cycles in a permutation. Picking up on this hint we may try the following.

We write all $n!$ permutations of $\{1,\ldots,n\}$ as products of disjoint cycles and count the total number of cycles, including repetitions. Any particular cycle $(x_1\ \ldots\ x_k)$ occurs once for every permutation of $\{1,\ldots,n\}-\{x_1,\ldots,x_k\}$; that is, it occurs $(n-k)!$ times. There are $P(n,k)/k$ cycles of length $k$, so the answer to the question is $$\sum_{k=1}^n \frac{P(n,k)}{k}(n-k)!=n!(RHS)\ .$$ But I am unable to show that the answer is also $n!(LHS)$. The alternating signs and binomial coefficients suggest inclusion/exclusion, but I can't make it work. On the other hand, inclusion/exclusion is normally used to avoid counting repetitions, and here I do want to count repetitions, so perhaps I'm completely on the wrong track.

Any ideas?

• does $x(x-1)(x-2)\ldots (x-n+1) = {n \brack n} - {n \brack {n-1} + \ldots \pm {n \brack 1}$ have a inclusion-exclusion interpretation? – abel Jun 3 '14 at 12:35
• @abel not sure but I will think about it! Thanks for the suggestion. – David Jun 4 '14 at 1:30

## 1 Answer

You may have a look at my answer of the original question which arguments combinatorically based upon permutations of $n+1$ elements with two cycles and the inclusion-exclusion principle. ... And you're right, usually we use the IEP the other way round, namely transform at least information to exactly information! :-)