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?

$\endgroup$
  • 1
    $\begingroup$ Wolfram has a suggestion, which is beyond my comprehension. $\endgroup$ – Hendrik Jan Dec 9 '12 at 10:26
  • $\begingroup$ The same answer with maple $\frac{\psi(n+2)+\gamma}{n+2}$. $\endgroup$ – Mhenni Benghorbal Dec 9 '12 at 10:57
  • $\begingroup$ @Michael: can you add (as a one-liner) in what context you found the question? Just curious. $\endgroup$ – Hendrik Jan Dec 9 '12 at 16:21
15
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Michael Dec 9 '12 at 11:26
  • $\begingroup$ 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. $\endgroup$ – Mhenni Benghorbal Dec 9 '12 at 14:21
7
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you for re-activating this problem. I posted an answer that is somewhat more elementary. (+1). $\endgroup$ – Marko Riedel Apr 5 '17 at 21:40
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ you have missed all the binomial coefficients here $\endgroup$ – dexter04 Dec 9 '12 at 11:00
  • $\begingroup$ The integration of $x^{k+1}/k+1$ is $x^{k+2}/(k+1)(k+2)$ $\endgroup$ – Amr Dec 9 '12 at 11:03
  • $\begingroup$ Thanks, rectified the errors. $\endgroup$ – lab bhattacharjee Dec 9 '12 at 11:30
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.