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

Question

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.

Answer 1

For the solution see original post below

EDIT

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

ad (1)

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

ad (2)

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

ad (3)

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

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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