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?

  • 1
    [Wolfram](http://www.wolframalpha.com/input/?i=sum+%28%28%28-1%29%5Ek%2F%28k%2B1%29%5E2%29+%28n+choose+k%29%29+k%3D0+to+n) has a suggestion, which is beyond my comprehension.2012-12-09
  • 0
    The same answer with maple $\frac{\psi(n+2)+\gamma}{n+2}$.2012-12-09
  • 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
    You are absolutely right Antonio, I just got to the same expression using the fact $\sum \binom{n}{k}\frac{(-1)^k}{x+k} = x^{-1}\binom{x+n}{n}^{-1}$ and taking the derivative on both sides.2012-12-09
  • 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
    you have missed all the binomial coefficients here2012-12-09
  • 0
    The integration of $x^{k+1}/k+1$ is $x^{k+2}/(k+1)(k+2)$2012-12-09
  • 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} $$