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}$

Solution 1:

Added 2014-06-13: According to a comment of David I've added a somewhat closer inspection of the combinatorial aspects for $(1)$ and $(2)$ below. The challenge was to find a proper combinatorial interpretation for $l_k=n!\binom{n}{k}\frac{1}{k}$.

This is a sort of combinatorial proof of the identity above. As David already mentioned in his answer, a true combinatorial proof seems hardly possible if we consider the factor $\frac{1}{k}$. But, we can always write the Harmonic Number $H_n$ as

\begin{align*} H_n=\sum_{k=1}^{n}\frac{1}{k}=\frac{a_n}{n!} \end{align*}

with $a_n$ a natural number and we can try to find a combinatorial proof for the numerator $a_n$. So, we can interpret $H_n$ as arithmetical ratio of $a_n$ with $n!$ based upon combinatorial arguments.

The proof is based upon two ideas:

• Permutation of $n+1$ elements containing exactly two cycles and the

• Inclusion-Exclusion Principle (IEP).

First step: Permutation with two cycles. Let $(a_1,\dots,a_j)(a_{j+1},\dots,a_{n+1})$ be a permutation of $n+1$ elements with two cycles. We may assume that $a_1=1$ and denote the cycle with $a_1$ left cycle. We may also assume that $a_{j+1}$ is the smallest element of the right cycle.

Now, following is valid:

The number $e_k$ of Permutations of $n+1$ elements with two cycles whereby the right cycle contains exactly $k$ $(1\leq k\leq n)$ elements is \begin{align*} e_k = \frac{n!}{k} \end{align*}

First we choose $k$ elements from the $n$-element set $\{2,3,\dots,n+1\}$ ($1$ is fix on the first position in the left cycle). This can be done in $\binom{n}{k}$ ways. $k$ elements in the right cycle can be positioned in $(k-1)!$ ways ($a_{j+1}$ is fix on the first position of the right cycle), while the remaining $n-k$ elements can be arranged in $(n-k)!$ ways in the left cycle. We observe:

\begin{align*} e_k=\binom{n}{k}(k-1)!(n-k)!=\frac{n!}{k} \end{align*}

Since $k$ may vary from $1$ to $n$ we get

The number of permutations of $n+1$ elements with two cycles is \begin{align*} e_1+e_2+\dots+e_n=\sum_{k=1}^{n}\frac{n!}{k}=n!H_n \end{align*}

So, we get a combinatorial interpretation for $n!H_n$ based on the $e_k$ (RHS). Observe, the $e_k$ are providing information for exactly $k$ elements within the right cycle. Here we can think about the inclusion-exclusion principle (IEP) which transforms at least information to exactly information (and vice versa).

Second step: Inclusion-Exclusion Principle (IEP)

We now introduce $l_k$ denoting the number of permutations of $n+1$ elements with $k$ elements in the right cycle of length at least $k$.

• $\binom{m}{k}$ ... number of arrangements to select $k$ specific elements from the right cycle of length $m(\geq k)$ of permutations with $n$ elements

• $e_k$ ... number of permutations with exactly $k$ elements in the right cycle

• $l_k$ ... number of permutations with $k$ elements in the right cycle of length at least $k$

Observe, that \begin{align*} l_k&=\sum_{m=k}^{n}\binom{m}{k}e_m\qquad\qquad1\leq k\leq n\tag{1}\\ &=n!\binom{n}{k}\frac{1}{k}=\binom{n}{k}e_k\tag{2} \end{align*}

Now a closer inspection of $l_k$ to identify more precisely the meaning of the number of permutations with $k$ elements in the right cycle of length at least $k$:

Combinatorial interpretation of $(1)$: $l_k=\sum_{m=k}^{n}\binom{m}{k}e_m$

Each summand of the RHS is of the form $\binom{m}{k}e_m$ with $k \leq m \leq n$. Since $e_m$ counts the number of permutations with right cycle length $m$, there are $\binom{m}{k}$ possibilities to choose a right cycle of length $k$ from those. Since $m$ varies from $k$ up to $n$ we get all permutations with $k$ elements in the right cycle of length at least $k$.

If we focus on a specific permutation with right cycle of length $m$ we can identify $\binom{m}{k}$ permutations with right cycle length $k$ by respecting the order of the elements within the left cycle and also by respecting the order of the elements within the right cycle. (See the next section for a more detailed explanation of this order respecting aspect).

Somewhat more demanding:

Combinatorial interpretation of $(2)$: $l_k = n!\binom{n}{k}\frac{1}{k}=\binom{n}{k}e_k$

The RHS $\binom{n}{k}e_k$ multiplies each occurrence of a permutation with right cycle of length $k$ with $\binom{n}{k}$.

Let's focus on a specific permutation with right cycle of length $k$ to find out how at least information is brought into play:

\begin{align*} (1, a_2,a_3,\dots,a_{n-k+1})(a_{n-k+2},a_{n-k+3},\dots,a_{n+1})\tag{3} \end{align*} We consider the $n$ positions starting with the first one occupied by $a_2$ and the last one occupied by $a_{n+1}$ and we can select $k$ out of these $n$ positions in $\binom{n}{k}$ ways. No we do following: We fill these $k$ selected positions with the $k$ elements of the right cycle by preserving their order. So, $a_{n-k+2}$ is left from $a_{n-k+3}$, which is left from $a_{n-k+4}$ up to $a_n$ which is left from $a_{n+1}$. Next we fill the remaining $n-k$ positions with the elements from the left cycle with $a_2, a_3$ up to $a_{n-k+1}$ also by preserving their order. So, $a_2$ is left from $a_3$, etc.

For each of these selections we define the right cycle starting with $a_{n-k+2}$ which was the leftmost (smallest) element of the right cycle in $(3)$. If $a_{n-k+2}$ is not the smallest element, we may rotate the cycle, so that the smallest element of the right cycle becomes the leftmost (bjiective operation).

We observe: By these operations we get $\binom{n}{k}$ permutations with right cycle length $\geq k$ and $\leq n$ and by additionally preserving the order of both cycles. So, we have identified all permutations of length at least $k$ which contain a specific permutation like $(3)$.

According to the IEP we get

\begin{align*} e_1+e_2+\cdots+e_n&=l_1-l_2\pm\cdots+(-1)^{n-1}l_n\\ n!H_n&=n!\sum_{k=1}^{n}(-1)^{k+1}\binom{n}{k}\frac{1}{k}\tag{4}\\ \end{align*}

So, we have shown:

• RHS: $n!H_n=n!\sum_{k=1}^{n}\frac{1}{k}$ gives the number of permutations of $n+1$ elements with two cycles, whereby each summand $\frac{n!}{k}$ gives the number of permutations of right cycles with length exactly $k$

• LHS: $n!\sum_{k=1}^{n}(-1)^{k+1}\binom{n}{k}\frac{1}{k}$ gives also the number of permutations of $n+1$ elements with two cycles, whereby each summand $n!\binom{n}{k}\frac{1}{k}$ gives the number of arrangements of $k$ elements in the right cycle with length at least $k$.

Some further notes:

Note: Identity $(4)$ gives rise to a so-called binomial inverse pair with Harmonic Numbers $H_n$ \begin{align*} H_n=\sum_{k=1}^{n}\binom{n}{k}\frac{(-1)^{k+1}}{k}&&\frac{1}{n}=\sum_{k=1}^{n}\binom{n}{k}(-1)^{k+1}H_k \end{align*}

(You may look at the answer to question 730885 for more details and another proof of identity $(1)$ which is algebraically not combinatorically).

Note: The unsigned Stirling Numbers of the first kind $|s(n,k)|$ are strongly related to the combinatorial interpretation above. The $|s(n,k)|$ give the number of permutations with $n$ elements containing exactly $k$ cycles. We observe $$n!H_n=|s(n+1,2)|$$

This proof is based upon Theorem 1 of A Stirling Encounter with Harmonic Numbers and the IEP related question 749390.

Added 2014-06-10: Example: Permutation of $n+1=4$ elements

According to a comment of abel please find below an example with permutations of $4$ elements, showing the interconnections between $e_k$ and $l_k$.

The table below lists all $11$ permutation of $n+1=4$ elements with exactly $2$ cycles.

• the first column lists an identifier for each permutation
• the second column lists all $11$ permutations of $4$ elements with exactly $2$ cycles
• the third column titled $e_k$ lists the contributions of $e_1, e_2$ and $e_3$.
• all other columns list the contributions of $l_k\ (1\leq k\leq 3)$ for the corresponding right cycle in the header line

Please note this table lists

• $6 e_1, 3 e_2$ and $2 e_3$ resulting in a total of $e_1+e_2+e_3=11$ permutations $(=3!H_3)$
• $18 l_1, 9 l_2$ and $2 l_3$ resulting in a total of $l_1-l_2+l_3=11$ permutations $(=3!H_3)$

\begin{array}{rccccccccccc} Id&()(a_{j+1}\dots)&e_k&(2)\ &(3)\ &(4)\ &(23)\ &(24)\ &(34)\ &(234)\ &(243)&\\ \hline\\ 1&(123)(4)&e_1&-\ &-\ &l_1\ &-\ &-\ &-\ &-\ &-\ &\\ 2&(132)(4)&e_1&-\ &-\ &l_1\ &-\ &-\ &-\ &-\ &-\ &\\ 3&(124)(3)&e_1&-\ &l_1\ &-\ &-\ &-\ &-\ &-\ &-\ &\\ 4&(142)(3)&e_1&-\ &l_1\ &-\ &-\ &-\ &-\ &-\ &-\ &\\ 5&(134)(2)&e_1&l_1\ &-\ &-\ &-\ &-\ &-\ &-\ &-\ &\\ 6&(143)(2)&e_1&l_1\ &-\ &-\ &-\ &-\ &-\ &-\ &-\ &\\ 7&(12)(34)&e_2&-\ &l_1\ &l_1\ &-\ &-\ &l_2\ &-\ &-\ &\\ 8&(13)(24)&e_2&l_1\ &-\ &l_1\ &-\ &l_2\ &-\ &-\ &-\ &\\ 9&(14)(23)&e_2&l_1\ &l_1\ &-\ &l_2\ &-\ &-\ &-\ &-\ &\\ 10&(1)(234)&e_3&l_1\ &l_1\ &l_1\ &l_2\ &l_2\ &l_2\ &l_3\ &-\ &\\ 11&(1)(243)&e_3&l_1\ &l_1\ &l_1\ &l_2\ &l_2\ &l_2\ &-\ &l_3\ & \end{array}

According to the table entries of $e_k$ and $l_k$ above we observe

\begin{align*} &e_1=\sum_{m=1}^{3}(-1)^{m+1}\binom{m}{1}l_m=\binom{1}{1}l_1-\binom{2}{1}l_2+\binom{3}{1}l_3=18-18+6=6\\ &e_2=\sum_{m=2}^{3}(-1)^{m+2}\binom{m}{2}l_m=\binom{2}{2}l_2-\binom{3}{2}l_3=9-6=3\\ &e_3=\sum_{m=3}^{3}(-1)^{m+3}\binom{m}{3}l_m=\binom{3}{3}l_3=2\\ \\ &l_1=\sum_{m=1}^{3}\binom{m}{1}e_m=\binom{1}{1}e_1+\binom{2}{1}e_2+\binom{3}{1}e_3=6+2\cdot3+3\cdot2=18\\ &l_2=\sum_{m=2}^{3}\binom{m}{2}e_m=\binom{2}{2}e_2+\binom{3}{2}e_3=3+3\cdot2=9\\ &l_3=\sum_{m=3}^{3}\binom{m}{3}e_m=\binom{3}{3}e_3=2\\ \\ &l_1=3!\binom{3}{1}\frac{1}{1}=6\cdot3\cdot1=18\\ &l_2=3!\binom{3}{2}\frac{1}{2}=6\cdot3\cdot\frac{1}{2}=9\\ &l_3=3!\binom{3}{3}\frac{1}{3}=6\cdot1\cdot\frac{1}{3}=2\\ \end{align*}

It follows:

\begin{array}{llll} 3!H_3&=e_1+e_2+e_3&=6+3+2&=11\\ 3!H_3&=l_1-l_2+l_3&=18-9+2&=11 \end{array}

Solution 2:

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.

Solution 3:

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 $$