I am trying to evaluate the following sum :

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

which is the same as

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

My approach so far has been aimed at converting this sum to a known form (given as a standard result in Integrals and series by Prudnikov et.al.)

$\displaystyle\sum_{k=1}^n(-1)^{k+1}{n\choose k} {{n+k}\choose k} \frac{1}{k}=\sum_{k=1}^n\frac{1}{k}$

I thought of combining the like terms ${n\choose k} {{n+k}\choose k}$ in the two series but that again depends on whether $n$ is even or odd. Any suggestion to proceed further ?


3 Answers 3


There is a neat trick. The shifted Legendre polynomials fulfill $$ Q_n(x)=P_n(2x-1)=\sum_{k=0}^{n}(-1)^{n+k}\binom{n}{k}\binom{n+k}{k}x^k \tag{1}$$ hence our sum is given by $$ S_n=\sum_{k=0}^{n}(-1)^{n+k}\binom{n}{k}\binom{n+k}{k}\frac{1}{k+2}=\int_{0}^{1}x\, Q_n(x)\,dx \tag{2}$$ and $$\boxed{\quad S_0=\frac{1}{2},\qquad S_1=\frac{1}{6},\qquad S_{n\geq 2}=0\quad}\tag{3} $$ follow from $x=\frac{Q_0(x)+Q_1(x)}{2}$ and the orthogonality relations for Legendre polynomials.

  • $\begingroup$ (+1) It might be nice to mention the value of the square integral of the Legendre Polynomials (at least for $P_0$ and $P_1$). $\endgroup$
    – robjohn
    Aug 29, 2016 at 8:02

$$ \begin{align} &\sum_{k=0}^n(-1)^{n+k}\binom{n}{k}\binom{n+k}{n}\frac1{k+2}\\[6pt] &=\sum_{k=0}^n(-1)^{n+k}\binom{n}{k}\binom{n+k}{k}\left(\frac1{k+1}-\frac1{(k+1)(k+2)}\right)\tag{1}\\[6pt] &=\frac1{n+1}\sum_{k=0}^n(-1)^{n+k}\binom{n+1}{k+1}\binom{n+k}{k}\\ &-\frac1{(n+1)(n+2)}\sum_{k=0}^n(-1)^{n+k}\binom{n+2}{k+2}\binom{n+k}{k}\tag{2}\\[6pt] &=\frac{(-1)^n}{n+1}\sum_{k=0}^n\binom{n+1}{n-k}\binom{-n-1}{k}\\ &-\frac{(-1)^n}{(n+1)(n+2)}\sum_{k=0}^n\binom{n+2}{n-k}\binom{-n-1}{k} \tag{3}\\[6pt] &=\frac{(-1)^n}{n+1}\binom{0}{n}-\frac{(-1)^n}{(n+1)(n+2)}\binom{1}{n}\tag{4}\\[6pt] &=\bbox[5px,border:2px solid #C0A000]{\left\{\begin{array}{} \frac12&\text{if }n=0\\ \frac16&\text{if }n=1\\ 0&\text{if }n\ge2 \end{array}\right.}\tag{5} \end{align} $$ Explanation:
$(1)$: $\frac1{k+2}=\frac1{k+1}-\frac1{(k+1)(k+2)}$ and $\binom{n+k}{n}=\binom{n+k}{k}$
$(2)$: $\frac1{k+1}\binom{n}{k}=\frac1{n+1}\binom{n+1}{k+1}$ applied once to the first sum and twice to the second
$(3)$: $\binom{n+j}{k+j}=\binom{n+j}{n-k}$ and $\binom{n+k}{k}=(-1)^k\binom{-n-1}{k}$
$(4)$: Vandermonde's Identity
$(5)$: evaluate at $n=0$ and $n=1$, and for $n\ge2$, $\binom{0}{n}=\binom{1}{n}=0$

  • 1
    $\begingroup$ i admire your ability to perform many complicated summations by only using elementary calculus (+1) $\endgroup$
    – tired
    Aug 29, 2016 at 7:43

Suppose we seek to evaluate

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

This is

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

The first piece here is

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

and the second

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

Re-write the first piece as

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


$${n+k-1\choose k-1} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k}} (1+z)^{n+k-1} \; dz.$$

This vanishes when $k=0$ so we may lower the index to zero to get for the sum

$$\frac{(-1)^{n+1}}{n+1}\frac{1}{2\pi i} \int_{|z|=\epsilon} (1+z)^{n-1} \sum_{k=0}^{n+1} {n+1\choose k} (-1)^k \frac{(1+z)^k}{z^k} \; dz \\ = \frac{(-1)^{n+1}}{n+1}\frac{1}{2\pi i} \int_{|z|=\epsilon} (1+z)^{n-1} \left(1-\frac{1+z}{z}\right)^{n+1} \; dz \\ = \frac{(-1)^{n+1}}{n+1}\frac{1}{2\pi i} \int_{|z|=\epsilon} (1+z)^{n-1} \frac{(-1)^{n+1}}{z^{n+1}} \; dz.$$

This is $$\frac{(-1)^{n+1}}{n+1}(-1)^{n+1} [z^n] (1+z)^{n-1} = 0$$

for $n\ge 1$. For $n=0$ we get

$$\frac{(-1)^{n+1}}{n+1}(-1)^{n+1} [z^0] \frac{1}{1+z} = 1.$$

Re-write the second piece as

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


$${n+k-2\choose k-2} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k-1}} (1+z)^{n+k-2} \; dz.$$

This vanishes when $k=1$ and $k=0$ so we may lower the limit of the sum to zero, getting for the sum

$$\frac{(-1)^n}{(n+1)(n+2)} \frac{1}{2\pi i} \int_{|z|=\epsilon} z (1+z)^{n-2} \sum_{k=0}^{n+2} {n+2\choose k} (-1)^k \frac{(1+z)^k}{z^k} \; dz \\ = \frac{(-1)^n}{(n+1)(n+2)} \frac{1}{2\pi i} \int_{|z|=\epsilon} z (1+z)^{n-2} \left(1-\frac{1+z}{z}\right)^{n+2} \; dz \\ = \frac{(-1)^n}{(n+1)(n+2)} \frac{1}{2\pi i} \int_{|z|=\epsilon} z (1+z)^{n-2} \frac{(-1)^{n+2}}{z^{n+2}} \; dz \\ = \frac{(-1)^n}{(n+1)(n+2)} \frac{1}{2\pi i} \int_{|z|=\epsilon} (1+z)^{n-2} \frac{(-1)^{n+2}}{z^{n+1}} \; dz.$$

This is $$\frac{(-1)^n}{(n+1)(n+2)} (-1)^{n+2} [z^n] (1+z)^{n-2} = 0$$

for $n\ge 2.$ For $n=0$ we get

$$\frac{(-1)^n}{(n+1)(n+2)} (-1)^{n+2} [z^0] \frac{1}{(1+z)^2} = \frac{1}{2}.$$

For $n=1$ we get

$$\frac{(-1)^n}{(n+1)(n+2)} (-1)^{n+2} [z^1] \frac{1}{1+z} = - \frac{1}{6}.$$

Collecting everything we get $1/2$ for $n=0$ and $1/6$ for $n=1$ and zero otherwise.

  • $\begingroup$ (+1) A tour de force. Nice job as always, but I still prefer shifted Legendre polynomials :D $\endgroup$ Aug 26, 2016 at 21:45
  • $\begingroup$ (+1) To you as well. The above what I wrote is only moderately pretty as we have repetition (two very similar computations). I guess it can serve as a basic example of the Egorychev method, possibly inducing the reader to want to learn more about it. $\endgroup$ Aug 26, 2016 at 22:27
  • $\begingroup$ (+1) The idea is similar to mine, but the integrals replace negative binomial coefficients and Vandermonde's Identity. $\endgroup$
    – robjohn
    Aug 29, 2016 at 7:50

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.