# (Combinatorial?) Proof of the identity $\sum_{k=1}^n \frac {(-1)^k}{k\,(k+1)}\binom nk = \frac 12 + \frac 13 + \dots + \frac 1{n+1}$?

Recently I've come across an interesting identity: $$\frac 1{1\cdot 2}\binom n1 - \frac 1{2\cdot 3}\binom n2 + \frac 1{3\cdot 4}\binom n3 - \dots + \frac {(-1)^n}{n\cdot (n+1)}\binom nn = \frac 12 + \frac 13 + \dots + \frac 1{n+1}.$$

Does anyone have an idea how to prove this?

PS. It'd be of special interest if someone could provide a combinatorial approach to this problem, although I'm not sure if that'd make sense since this is an identity for non-integer.

Edit: Perhaps my question was worded in a way that seems trivial since there's a vote to close this question. I should have mentioned that I can prove it by expanding $$\frac 1{k(k-1)}$$ and do some further calculation. What I want is a clever way to interpret it, e.g. using combinatorics or some kind of generating function or integration.

• The left-hand side comes from integrating $((1-x)^n-1)/x$ twice. The right- hand side might result from the substitution $y=1-x$ Sep 22, 2018 at 11:24
• @Empy2 That's an interesting way to view this. Thanks. Sep 22, 2018 at 11:26
• A possible direction to go would be to rewrite the sum $1 + \frac12 + \frac13 + \dots + \frac1n$ as $\frac{1}{n!}\left[n+1 \atop 2\right]$, where $\left[n \atop k\right]$ is a Stirling number of the first kind. Sep 22, 2018 at 21:45
• The right answer is a $\large\texttt{negative number}$: $\displaystyle\color{red}{\Large -}\left({1 \over 2} + {1 \over 3} + \cdots + {1 \over n + 1}\right)$. Nov 15, 2018 at 17:24

For the solution see original post below

EDIT

Here are direct proofs of (1), (2), and (3), each in one sequence

$$H_{n} = \sum_{k=1}^n \frac{1}{k} = \sum_{k=1}^n \int_0^1 y^{k-1}= \int_0^1\,dy \sum_{k=1}^n y^{k-1}= \int_0^1\,dy \frac{1-y^n}{1-y} \\({y\to 1-x})=\int_0^1\,dx \frac{1}{x} \left(1-(1-x)^n\right)= \int_0^1\,dx \sum_{k=1}^n (-1)^{k+1}\binom{n}{k} x^{k-1} \\= \sum_{k=1}^n (-1)^{k+1}\binom{n}{k}\int_0^1\,dx\; x^{k-1} = \sum_{k=1}^n (-1)^{k+1}\binom{n}{k}\frac{1}{k}$$

QED.

$$\sum _{k=1}^n \frac{(-1)^{k+1} }{k+1}\binom{n}{k}=\sum _{k=1}^n (-1)^{k+1}\binom{n}{k} \int_0^1 x^k \,dx =\int_0^1 \,dx \sum _{k=1}^n (-1)^{k+1}\binom{n}{k} x^k \\= \int_0^1 \, dx \left(1-(1-x)^n\right)= 1-\frac{1}{n+1} = \frac{n}{n+1}$$

QED.

$$\sum _{k=1}^n (-1)^{k+1} \binom{n}{k} \frac{1}{a+k}=\sum_{k=1}^n (-1)^{k+1} \binom{n}{k} \int_0^1 \,dx x^{a+k-1}\\=\int_0^1\,dx x^{a-1} \sum _{k=1}^n (-1)^{k+1} \binom{n}{k} x^{k}=\int_0^1\,dx x^{a-1} \left(1-(1-x)^n\right)\\= \frac{1}{a} - \int_0^1\,dx x^{a-1} (1-x)^n= \frac{1}{a} - \text{Beta}(a,n+1)= \frac{1}{a} - \frac{\Gamma(a) \Gamma(n+1)}{\Gamma(a+n+1)}$$

QED.

Remark

Combining (3) and (1) we see that

$$H_{n} = \lim_{a\to0}\left( \frac{1}{a} - \frac{\Gamma(a) \Gamma(n+1)}{\Gamma(a+n+1)}\right)\tag{4a}$$

To make this explicit we write the r.h.s as

$$\frac{1}{a} \left( 1- \frac{\Gamma(a+1) \Gamma(n+1)}{\Gamma(a+n+1)}\right)=\frac{\Gamma(a+n+1)-\Gamma(a+1) \Gamma(n+1)}{a\Gamma(a+n+1)}$$

and then apply l'Hospital to arrive at

$$H_{n} =\frac{ \frac{\partial (\Gamma (a+n+1)-n! \Gamma (a+1))}{\partial a}\text{/.}\, a\to 0} {\frac{\partial (a \Gamma (a+n+1))}{\partial a}\text{/.}\, a\to 0} = \frac{ \Gamma' (n+1)-n! \Gamma' (1)} {\Gamma(n+1)}\\= \frac{ \Gamma' (n+1)}{\Gamma(n+1)}+ \gamma = \frac{\partial \log (\Gamma (n+1))}{\partial n}+\gamma= \psi ^{(0)}(n+1)+\gamma\tag{4b}$$

Here $$\gamma= -\Gamma'(1)$$ is the Euler-Mascheroni constant and $$\psi$$ is the polygamma function.

Original post

This is not the requested combinatorical interpretation but there are some interesting identities popping up.

Subtracting these two interesting relations

$$\sum _{k=1}^n \frac{(-1)^{k+1}}{k} \binom{n}{k} = H_{n}\tag{1}$$

and

$$\sum _{k=1}^n \frac{(-1)^{k+1}}{1+k} \binom{n}{k} = \frac{n}{1+n}\tag{2}$$

and observing

$$\frac{1}{k}-\frac{1}{1+k}= \frac{1}{k(k+1)}$$

we find that the left hand side is that of the formula we have to prove while the right hand side gives

$$H_{n}-\frac{n}{1+n} = H_{n+1}-1$$

which proves the OP.

Here we have used the basic relation

$$H_{n}+\frac{1}{1+n} =H_{n+1}$$

Remarks

1) I found it surprising that the small difference in the l.h.s. of (1) and (2) leads to a apreciably different results.

2) formulas (1) and (2) can be generalized to

$$\sum _{k=1}^n \frac{(-1)^{k+1}}{a+k} \binom{n}{k} = \frac{1}{a}-\frac{\Gamma (a) \Gamma (n+1)}{\Gamma (a+n+1)}\tag{3}$$

• Very interesting! Thanks. Sep 22, 2018 at 17:43

Hint: $$\frac{1}{k\cdot(k+1)}\binom{n}{k}=\Big(\frac{(k+1)-k}{k\cdot (k+1)}\Big)\binom{n}{k}=\Big(\frac{1}{k}-\frac{1}{k+1} \Big)\binom{n}{k}$$

• Indeed this is a way to prove it. What I meant to ask was perhaps "Is there a combinatorial way to view the identity?". Regardless, thank you for you answer. Sep 22, 2018 at 11:25
• @BigbearZzz I don't think so, but, there may be a probabilistic interpretation of this sum. Sep 22, 2018 at 11:27
• If you manage to figure out an interpretation please do tell. I haven't done any combinatorics or probability for too long to think of anything interesting to say about this question. Sep 22, 2018 at 11:34
• @BigbearZzz Of course! Sep 22, 2018 at 11:39

Answer to the Question \begin{align} f(n) &=\sum_{k=1}^n\frac{(-1)^{k-1}}{k(k+1)}\binom{n}{k}\tag1\\ &=\sum_{k=1}^n\frac{(-1)^{k-1}}{k(k+1)}\left[\binom{n-1}{k}+\binom{n-1}{k-1}\right]\tag2\\ &=\sum_{k=1}^{n-1}\frac{(-1)^{k-1}}{k(k+1)}\binom{n-1}{k} +\frac1{n(n+1)}\sum_{k=1}^n(-1)^{k-1}\binom{n+1}{k+1}\tag3\\ &=f(n-1)+\frac1{n(n+1)}\sum_{k=-1}^0(-1)^k\binom{n+1}{k+1}\tag4\\ &=f(n-1)+\frac1{n+1}\tag5\\[9pt] &=H_{n+1}-1\tag6 \end{align} Explanation:
$$(1)$$: define $$f$$
$$(2)$$: Pascal's Rule
$$(3)$$: $$n(n+1)\binom{n-1}{k-1}=k(k+1)\binom{n+1}{k+1}$$
$$(4)$$: apply the Binomial Theorem to $$(1-1)^{n+1}$$
$$(5)$$: evaluate the sum
$$(6)$$: solve the recurrence

Proof for $$\boldsymbol{(1)}$$ from Dr. Wolfgang Hintze's Answer

This proceeds in much the same fashion as the answer above, so I will include it. \begin{align} g(n) &=\sum_{k=1}^n\frac{(-1)^{k-1}}{k}\binom{n}{k}\tag{a}\\ &=\sum_{k=1}^n\frac{(-1)^{k-1}}{k}\left[\binom{n-1}{k}+\binom{n-1}{k-1}\right]\tag{b}\\ &=g(n-1)+\frac1n\sum_{k=1}^n(-1)^{k-1}\binom{n}{k}\tag{c}\\ &=g(n-1)+\frac1n\tag{d}\\[12pt] &=H_n\tag{e} \end{align} Explanation:
$$\text{(a)}$$: define $$g$$
$$\text{(b)}$$: Pascal's Rule
$$\text{(c)}$$: $$n\binom{n-1}{k-1}=k\binom{n}{k}$$
$$\text{(d)}$$: apply the Binomial Theorem to $$(1-1)^n$$
$$\text{(e)}$$: solve the recurrence

• @ robjohn It is always a pleasure to see your clearly laid out solutions. Sep 23, 2018 at 8:25

Here is a (shy) attempt to give a combinatorical interpretation of the simpler formula

$$\sum _{k=1}^n \frac{(-1)^{k+1}}{k} \binom{n}{k} = H_{n}\tag{2.1}$$

using the inclusion/exclusion principle.

Consider a set of subsets $$A_{i}, i=1..n$$ and define a measure $$N(.)$$ with the property

$$N(A_{i})=1, N(A_{i}\cap A_{j})=\frac{1}{2},N(A_{i}\cap A_{j}\cap A_{k})=\frac{1}{3}, ... \tag{2.2}$$

Then the measure for the union of the sets, i.e. the expression

$$x=N(A_{1}\cup A_{2}\cup ...\cup A_{n})$$

expands into, considering the case $$n=3$$,

$$x= N(A_{1})+N(A_{2})+N(A_{3}) \\- N(A_{1}\cap A_{2})-N(A_{1}\cap A_{3})-N(A_{2}\cap A_{3}) \\+ N(A_{1} \cap A_{2} \cap A_{3})$$

This can now be written as

$$x=\\ 3 N(A_{1})-3 N(A_{1}\cap A_{2})+N(A_{1} \cap A_{2} \cap A_{3}) \\ =\binom{3}{1} \frac{1}{1} - \binom{3}{2} \frac{1}{2} + \binom{3}{3} \frac{1}{3}$$

which is exactly the l.h.s. of (2.1) for $$n=3$$.

This now generalises to any $$n=1, 2, 3, ...$$.

That this measure of the union is given by $$H_{n}$$ is a result which at least I am not able to derive independently. Hence the attempted interpretation is incomplete.

I'd like to ask the reader for strong criticism and improvement of this attempt.

• The total measure of the area that belongs to exactly $k$ sets is $1/k$, eg. $(A_1\cap A_2^c\cap A_3^c) \cup (A_1^c\cap A_2\cap A_3^c) \cup (A_1^c\cap A_2^c \cap A_3)$ Sep 23, 2018 at 15:16
• So the measure with a specific $k$ sets and no other is $1/k{n\choose k}=1/n{n-1\choose k-1}$. To confirm, the measure with a specific $k$ sets and perhaps others is $\sum_i{n-k\choose i}\frac{1}{n{n-1\choose i-1}}$ but that might be as difficult as the original problem. Sep 25, 2018 at 9:22

$$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$$

$$\ds{\sum_{k = 1}^{n}{\pars{-1}^{k} \over k\pars{k + 1}} {n \choose k} = \color{red}{\large -}\pars{{1 \over 2} + {1 \over 3} + \cdot +{1 \over n + 1}}:\ {\LARGE ?}}$$.

\begin{align} &\bbox[10px,#ffd]{\sum_{k = 1}^{n}{\pars{-1}^{k} \over k\pars{k + 1}}{n \choose k}} = \sum_{k = 1}^{n}{n \choose k}\pars{-1}^{k} \pars{\int_{0}^{1}x^{k - 1}\,\dd x} \pars{\int_{0}^{1}y^{k}\,\dd y} \\[5mm] = &\ \int_{0}^{1}\int_{0}^{1} \sum_{k = 1}^{n}{n \choose k}\pars{-xy}^{k} \,{\dd x \over x}\,\dd y = \int_{0}^{1}\int_{0}^{1} {\pars{1 - xy}^{n} - 1 \over x}\,\dd x\,\dd y \\[5mm] = &\ \int_{0}^{1}\int_{0}^{y} {\pars{1 - x}^{n} - 1 \over x}\,\dd x\,\dd y = \int_{0}^{1}{\pars{1 - x}^{n} - 1 \over x}\int_{x}^{1} \,\dd y\,\dd x \\[5mm] = &\ \int_{0}^{1}{\pars{1 - x}^{n} - 1 \over x} \,\pars{1 - x}\,\dd x = \int_{0}^{1}x\,{x^{n} - 1 \over 1 - x}\,\dd x \\[5mm] = &\ \int_{0}^{1}\pars{-\sum_{k = 1}^{n}x^{k}}\,\dd x = -\sum_{k = 1}^{n}\int_{0}^{1}x^{k}\,\dd x= -\sum_{k = 1}^{n}{1 \over k + 1} \\[5mm] = &\ \bbx{-\,{1 \over 2} - {1 \over 3} - \cdots - {1 \over n + 1}} \end{align}