14
$\begingroup$

How can I calculate the following sum involving binomial terms:

$\sum_{k=0}^{n} \binom{n}{k}\frac{(-1)^k}{(k+1)^2}$

Where the value of n can get very big (thus calculating the binomial coefficients is not feasible).

Is there a closed form for this summation?

  • 0
    @Michael: can you add (as a one-liner) in what context you found the question? Just curious.2012-12-09

8 Answers 8

15

Apparently I'm a little late to the party, but my answer has a punchline!

We have $ \frac{1}{z} \int_0^z \sum_{k=0}^{n} \binom{n}{k} s^k\,ds = \sum_{k=0}^{n} \binom{n}{k} \frac{z^k}{k+1}, $ so that $ - \int_0^z \frac{1}{t} \int_0^t \sum_{k=0}^{n} \binom{n}{k} s^k\,ds\,dt = - \sum_{k=0}^{n} \binom{n}{k} \frac{z^{k+1}}{(k+1)^2}. $ Setting $z = -1$ gives an expression for your sum, $ \sum_{k=0}^{n} \binom{n}{k} \frac{(-1)^k}{(k+1)^2} = \int_{-1}^{0} \frac{1}{t} \int_0^t \sum_{k=0}^{n} \binom{n}{k} s^k\,ds\,dt. $ Now, $\sum_{k=0}^{n} \binom{n}{k} s^k = (1+s)^n$, so $ \begin{align*} \sum_{k=0}^{n} \binom{n}{k} \frac{(-1)^k}{(k+1)^2} &= \int_{-1}^{0} \frac{1}{t} \int_0^t (1+s)^n \,ds\,dt \\ &= \frac{1}{n+1}\int_{-1}^{0} \frac{1}{t} \left[(1+t)^{n+1} - 1\right]\,dt \\ &= \frac{1}{n+1}\int_{0}^{1} \frac{u^{n+1}-1}{u-1}\,du \\ &= \frac{1}{n+1}\int_0^1 \sum_{k=0}^{n} u^k \,du \\ &= \frac{1}{n+1}\sum_{k=1}^{n+1} \frac{1}{k} \\ &= \frac{H_{n+1}}{n+1}, \end{align*} $ where $H_n$ is the $n^{\text{th}}$ harmonic number.

  • 0
    Just to confirm your answer with the others in the comment, here is the relation between the $\psi$ function and the harmonic numbers $ H_n=\gamma+\psi_0(n+1)$. See [here](http://mathworld.wolfram.com/HarmonicNumber.html).2012-12-09
7

I'm even later to the party, but that's only because "absorption identity" kept yelling in my ear. :)

One application of the absorption identity gets one of the factors of $k+1$ out of the denominator: $\begin{align} \sum_{k=0}^n \binom{n}{k} \frac{(-1)^k}{(k+1)^2} &= \frac{1}{n+1} \sum_{k=0}^n \binom{n+1}{k+1} \frac{(-1)^k}{k+1} \\ &= \frac{1}{n+1} \sum_{k=1}^{n+1} \binom{n+1}{k} \frac{(-1)^{k+1}}{k} \end{align}.$ It would be nice to use the absorption identity again, but we need a $k+1$ in the denominator of the summand rather than a $k$. By using the basic binomial coefficient recursion formula, we can make that happen.

Let $\displaystyle f(n) = \sum_{k=1}^{n} \binom{n}{k} \frac{(-1)^{k+1}}{k}.$ Then looking at the difference of $f(n+1)$ and $f(n)$ gives us $\begin{align} f(n+1) - f(n) &= \sum_{k=1}^{n+1} \binom{n+1}{k} \frac{(-1)^{k+1}}{k} - \sum_{k=1}^n \binom{n}{k} \frac{(-1)^{k+1}}{k} \\ &= \sum_{k=1}^{n+1} \binom{n}{k-1} \frac{(-1)^{k+1}}{k} \\ &= \sum_{k=0}^n \binom{n}{k} \frac{(-1)^{k}}{k+1} \\ &= \frac{1}{n+1}\sum_{k=0}^n \binom{n+1}{k+1} (-1)^{k} \:\:\:\: \text{ (absorption identity!)} \\ &= \frac{1}{n+1} \left(1 + \sum_{k=0}^{n+1} \binom{n+1}{k} (-1)^{k+1} \right)\\ &= \frac{1}{n+1}, \end{align}$ where in the last step we used the fact that the alternating sum of the binomial coefficients is $0$.

Thus $f(n+1) = \sum_{k=0}^n (f(k+1) - f(k)) = \sum_{k=0}^n \frac{1}{k+1} = H_{n+1}.$

Therefore, $\sum_{k=0}^n \binom{n}{k} \frac{(-1)^k}{(k+1)^2} = \frac{H_{n+1}}{n+1}.$

2

$\newcommand{\bbx}[1]{\,\bbox[8px,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}$ \begin{align} \sum_{k = 0}^{n}{n \choose k}{\pars{-1}^{k} \over \pars{k + 1}^{2}} & = -\sum_{k = 0}^{n}{n \choose k}\pars{-1}^{k}\int_{0}^{1}\ln\pars{x}\,x^{k}\,\dd x = -\int_{0}^{1}\ln\pars{x}\sum_{k = 0}^{n}{n \choose k}\pars{-x}^{k}\,\dd x \\[5mm] & = -\int_{0}^{1}\ln\pars{x}\pars{1 - x}^{n}\,\dd x = \left.-\,\partiald{}{\mu}\int_{0}^{1}x^{\mu}\pars{1 - x}^{n}\,\dd x\, \right\vert_{\ \mu\ =\ 0} \\[5mm] & = \left.-\,\partiald{}{\mu}{\Gamma\pars{\mu + 1}\Gamma\pars{n + 1} \over \Gamma\pars{\mu + n + 2}}\,\right\vert_{\ \mu\ =\ 0} = \bbx{\ds{H_{n + 1} \over n + 1}} \end{align}

Note that $\ds{\Gamma\pars{a + \mu} = \Gamma\pars{a}\bracks{1 + \pars{H_{a - 1} - \gamma}\mu + \,\mrm{O}\pars{\mu^{2}}}}$ such that

\begin{align} -\,{\Gamma\pars{\mu + 1}\Gamma\pars{n + 1} \over \Gamma\pars{\mu + n + 2}} & = -\,{n! \over \pars{n + 1}!}\braces{1 + \bracks{\pars{1 - \gamma}-\pars{H_{n + 1} - \gamma}}\mu + \,\mrm{O}\pars{\mu^{2}}} \\[5mm] = &\ -\,{1 \over n + 1} + {H_{n} \over n + 1}\,\mu + \,\mrm{O}\pars{\mu^{2}}\qquad \mbox{with}\quad H_{0} = 0. \end{align}

  • 0
    Thank you for re-activating this problem. I posted an answer that is somewhat more elementary. (+1).2017-04-05
1

$(1-x)^n=\sum_{0\le k\le n}\binom nk(-1)^kx^k$

Integrating wrt $x,$

$-\frac{(1-x)^{n+1}}{n+1}+C=\sum_{0\le k\le n}\binom nk(-1)^k\frac{x^{k+1}}{k+1}$ where $C$ is the indefinite constant.

Putting $x=0,C-\frac1{n+1}=0\implies C=\frac1{n+1}$

So, $\sum_{0\le k\le n}\binom nk(-1)^k\frac{x^{k+1}}{k+1}=\frac1{n+1}-\frac{(1-x)^{n+1}}{n+1}$

So, $\sum_{0\le k\le n}\binom nk(-1)^k\frac{x^{k}}{k+1}=\frac1{x(n+1)}-\frac{(1-x)^{n+1}}{(n+1)x}$

Again integrating wrt $x,$

$\sum_{0\le k\le n}\binom nk(-1)^k\frac{x^{k+1}}{(k+1)^2}=\frac {\log x}{n+1}-\int\frac{(1-x)^{n+1}}{(n+1)x}dx+D$ where $D$ is the indefinite constant.

  • 0
    Thanks, rectified the errors.2012-12-09
1

An overkill. From the derivative version of the Melzak's identity $\sum_{k=0}^{n}\dbinom{n}{k}\left(-1\right)^{k}\frac{f\left(y-k\right)}{\left(x+k\right)^{2}}=\frac{f\left(x+y\right)\sum_{k=0}^{n}\frac{1}{k+x}-\frac{d}{dx}f\left(x+y\right)}{x\dbinom{x+n}{n}},\,x\neq-k$ where $f$ is a polynomial up to degree $n$ we have, taking $f\left(z\right)\equiv1,\,x=1$, that $\sum_{k=0}^{n}\dbinom{n}{k}\left(-1\right)^{k}\frac{1}{\left(1+k\right)^{2}}=\frac{\sum_{k=0}^{n}\frac{1}{k+1}}{n+1}=\color{red}{\frac{H_{n+1}}{n+1}}$ as wanted.

0

I don't if you would accept this:

$\sum_{k=0}^{n} \binom{n}{k}x^k=(1+x)^k$

Integrate with respect to $x$ from $0$ to $t$ to get: $\sum_{k=0}^{n} \binom{n}{k}\frac{t^{k+1}}{k+1}=\frac{(1+t)^{k+1}-1}{k+1}$

Now divide by $t$ to get: $\sum_{k=0}^{n} \binom{n}{k}\frac{t^{k}}{k+1}=\frac{(1+t)^{k+1}-1}{(k+1)t}$

Now interate agian with respect to $t$ from $0$ to $z$ to get:

$\sum_{k=0}^{n} \binom{n}{k}\frac{z^{k}}{(k+1)^2}=\int_{0}^z\frac{(1+t)^{k+1}-1}{(k+1)t}dt$ Now Let $z=-1$ $\sum_{k=0}^{n} \binom{n}{k}\frac{(-1)^{k}}{(k+1)^2}=\int_{0}^{-1}\frac{(1+t)^{k+1}-1}{(k+1)t}dt$

0

Suppose we seek to compute

$S_n = \sum_{k=0}^n {n\choose k} \frac{(-1)^k}{(k+1)^2}.$

With this in mind we introduce the function

$f(z) = n! (-1)^n \frac{1}{(z+1)^2} \prod_{q=0}^n \frac{1}{z-q}.$

We then obtain for $0\le k\le n$

$\mathrm{Res}_{z=k} f(z) = (-1)^n \frac{n!}{(k+1)^2} \prod_{q=0}^{k-1} \frac{1}{k-q} \prod_{q=k+1}^n \frac{1}{k-q} \\ = (-1)^n \frac{n!}{(k+1)^2} \frac{1}{k!} \frac{(-1)^{n-k}}{(n-k)!} = {n\choose k} \frac{(-1)^k}{(k+1)^2}.$

This means that

$S_n = \sum_{k=0}^n \mathrm{Res}_{z=k} f(z)$

and since residues sum to zero we have

$S_n + \mathrm{Res}_{z=-1} f(z) + \mathrm{Res}_{z=\infty} f(z) = 0.$

We can compute the residue at infinity by inspection (it is zero) or more formally through

$\mathrm{Res}_{z=\infty} n! (-1)^n \frac{1}{(z+1)^2} \prod_{q=0}^n \frac{1}{z-q} \\ = - n! (-1)^n \mathrm{Res}_{z=0} \frac{1}{z^2} \frac{1}{(1/z+1)^2} \prod_{q=0}^n \frac{1}{1/z-q} \\ = - n! (-1)^n \mathrm{Res}_{z=0} \frac{1}{(z+1)^2} \prod_{q=0}^n \frac{z}{1-qz} \\ = - n! (-1)^n \mathrm{Res}_{z=0} \frac{z^{n+1}}{(z+1)^2} \prod_{q=0}^n \frac{1}{1-qz} = 0.$

We get for the residue at $z=-1$ that

$\mathrm{Res}_{z=-1} f(z) = n! (-1)^n \left. \left(\prod_{q=0}^n \frac{1}{z-q}\right)'\right|_{z=-1} \\ = - n! (-1)^n \left. \left(\prod_{q=0}^n \frac{1}{z-q}\right) \sum_{q=0}^n \frac{1}{z-q} \right|_{z=-1} \\ = - n! (-1)^n \frac{(-1)^{n+1}}{(n+1)!} \left(-H_{n+1}\right) = -\frac{H_{n+1}}{n+1}.$

We thus have

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

or

$\bbox[5px,border:2px solid #00A000]{ \frac{H_{n+1}}{n+1}.}$

0

Let $ f(x)=\sum_{k=0}^n\binom{n}{k}\frac{(-1)^kx^{k+1}}{(k+1)^2} $ then $ \begin{align} f'(x) &=\sum_{k=0}^n\binom{n}{k}\frac{(-1)^kx^k}{(k+1)}\\ &=\frac1{n+1}\sum_{k=0}^n\binom{n+1}{k+1}(-1)^kx^k\\ &=\frac1{n+1}\frac{1-(1-x)^{n+1}}{x} \end{align} $ Therefore, $ \begin{align} \sum_{k=0}^n\binom{n}{k}\frac{(-1)^k}{(k+1)^2} &=f(1)\\ &=\frac1{n+1}\int_0^1\frac{1-(1-x)^{n+1}}{x}\,\mathrm{d}x\\ &=\frac1{n+1}\lim_{a\to1^-}\left[\int_0^1x^{-a}\,\mathrm{d}x-\int_0^1(1-x)^{n+1}x^{-a}\,\mathrm{d}x\right]\\ &=\frac1{n+1}\lim_{a\to1^-}\left[\frac1{1-a}-\frac{\Gamma(n+2)\Gamma(2-a)}{(1-a)\Gamma(n+3-a)}\right]\\ &=\frac1{n+1}\lim_{a\to1^-}\frac{1-(n+1)!\frac1{(n+2-a)(n+1-a)\cdots(2-a)}}{1-a}\\[3pt] &=\frac1{(n+1)(n+1)!}\lim_{a\to1^-}\frac{(n+2-a)(n+1-a)\cdots(2-a)-(n+1)!}{1-a}\\[3pt] &=\frac{H_{n+1}}{n+1} \end{align} $