# A sum including binomial coefficients

I would like to prove the following equality: $$\sum_k (-1)^{n-1}(-2)^k\binom{n}{k+1}\binom{n+k-1}{k}=\sum_{k=0}^{n-2}\binom{2n-k-2}{n-1}\binom{n-2}{k}$$

but the power over two and the switch on the number of sums bothers me. Any help would be welcome.

(the equality it part of Note 1.41 in the book "Analytic Combinatorics")

• The first binomial coefficient in the sum on the right hand side should be ${2n-k-2\choose n-1}$, not ${2n-k-2\choose n-2}$. – user940 Oct 22 '15 at 1:21
• you're right, there was a typo there – lea Oct 22 '15 at 7:17

The following answer is purely algebraic. We transform both sides of OPs expression to finally obtain the same representation. We also use the coefficient of operator $[z^n]$ to denote the coefficient $a_n$ of $z^n$ of a series $\sum_{k=0}^{\infty}a_kz^k$.

At first we transform the right-hand side. It's the easier one.

\begin{align*} \sum_{k=0}^{n-2}&\binom{2n-k-2}{n-1}\binom{n-2}{k}\\ &=\sum_{k=0}^{n-2}\binom{n+k}{n-1}\binom{n-2}{k}\tag{1}\\ &=\sum_{k=0}^{n-2}[z^{n-1}](1+z)^{n+k}\binom{n-2}{k}\tag{2}\\ &=[z^{n-1}](1+z)^n\sum_{k=0}^{n-2}\binom{n-2}{k}(1+z)^{k}\\ &=[z^{n-1}](1+z)^n(2+z)^{n-2}\tag{3}\\ &=\sum_{k=0}^{n-1}\left([z^k](1+z)^n\right)\left([z^{n-1-k}](2+z)^{n-2}\right)\\ &=\sum_{k=0}^{n-1}\binom{n}{k}\binom{n-2}{n-1-k}2^{(n-2)-(n-1-k)}\\ &=\sum_{k=1}^{n-1}\binom{n}{k}\binom{n-2}{k-1}2^{k-1}\tag{4}\\ \end{align*}

Comment:

• In (1) we change the order of summation by transforming the index $k$ with $n-2-k$

• In (2) we represent the binomial coefficient $\binom{n+k}{n-1}$ as the coefficient of $z^{n-1}$ of $(1+z)^{n+k}$

• In (3) we write the sum as polynomial $(2+z)^{n-2}$.

And here's the left-hand side.

\begin{align*} \sum_{k=0}^{n-1}&(-1)^{n-1}(-2)^k\binom{n}{k+1}\binom{n+k-1}{k}\\ &=(-1)^{n-1} \sum_{k=0}^{n-1}(-2)^k\binom{n}{k+1}\binom{n+k-1}{n-1}\\ &=(-1)^{n-1} \sum_{k=1}^{n}(-2)^{k-1}\binom{n}{k}\binom{n+k-2}{n-1}\\ &=\frac{1}{2}(-1)^{n-1} \sum_{k=1}^{n}(-2)^{k}\binom{n}{k}[z^{n-1}](1+z)^{n+k-2}\\ &=\frac{1}{2}(-1)^{n-1} [z^{n-1}](1+z)^{n-2}\sum_{k=1}^{n}\binom{n}{k}(-2)^k(1+z)^{k}\\ &=\frac{1}{2}(-1)^{n-1} [z^{n-1}](1+z)^{n-2}\left\{(-1-2z)^n-1\right\}\\ &=\frac{1}{2} [z^{n-1}](1+z)^{n-2}\left\{(1+2z)^n+1\right\}\tag{5}\\ &=\frac{1}{2} [z^{n-1}](1+z)^{n-2}(1+2z)^n\\ &=\frac{1}{2}\sum_{k=0}^{n-1}\left([z^k](1+2z)^n\right)\left([z^{n-1-k}](1+z)^{n-2}\right)\\ &=\frac{1}{2}\sum_{k=0}^{n-1}\binom{n}{k}2^k\binom{n-2}{k-1}\tag{6}\\ \end{align*}

Since the expressions (4) and (6) are equal, the claim follows.

The summand with $k=0$ does not contribute anything. So we can start with $k=1$ and after an index transformation we obtain the somewhat more convenient representation \begin{align*} \sum_{k=0}^{n-2}\binom{n}{k+1}\binom{n-2}{k}2^k \end{align*}

Comment:

• In (5) we need not to consider the summand $+1$ in the rightmost expression. It does not contribute anything to the coefficient $[z^{n-1}]$.
• (+1). Thanks for presenting this algebraic proof. Your generating functions would appear to be the same as what I had above. I appreciate seeing that we can do these proofs without residues. Sometimes we do need residues however as when we sum the residues of a rational function at its poles and the residue at infinity. – Marko Riedel Oct 23 '15 at 23:01
• @MarkoRiedel: Thanks, you're welcome and I agree with both of your statements. ... Since OP is referring to Flajolet, she will sooner or later also appreciate the somewhat more sophisticated techniques you present with considerable mastery! :-) – Markus Scheuer Oct 23 '15 at 23:08
• Thank you for your answer :-) . Which books would you recommend for someone to practice on these manipulations? – lea Oct 27 '15 at 19:34
• @lea: You're welcome! :-) I recommend Generatingfunctionology by H.S. Wilf and Concrete Mathematics by D. Knuth. You also might find this answer and this one helpful. Best regards, – Markus Scheuer Oct 27 '15 at 21:39

It seems there are some typesetting errors in this equality.

Suppose we seek to verify the closely related equality (obtained by a shift by one on the right)

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

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

This yields for the sum $$(-1)^{n-1} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^n} (1+z)^{n-1} \sum_{k=0}^{n+1} {n+1\choose k} (-2)^k (1+z)^k\; dz \\ = (-1)^{n-1} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^n} (1+z)^{n-1} (-1-2z)^{n+1} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^n} (1+z)^{n-1} (1+2z)^{n+1} \; dz.$$

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

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

Put $z=2w$ in this integral to obtain $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{2^n w^n} (1+2w)^{n+1} (2+2w)^{n-1} \; 2 dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^n} (1+2w)^{n+1} (1+w)^{n-1} \; dw.$$

This concludes the argument.

Addendum. Apparently there is another possible version of this equality which is

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

Re-write the LHS as $$(-1)^{n-1} \sum_{k=1}^{n} {n\choose k} (-2)^{k-1} {n+k-2\choose k-1}.$$

We may extend this to include zero because the second binomial coefficent is zero then, getting $$(-1)^{n-1} \sum_{k=0}^{n} {n\choose k} (-2)^{k-1} {n+k-2\choose k-1}.$$

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

This yields for the sum $$(-1)^{n-1} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^n} (1+z)^{n-2} \sum_{k=0}^n {n\choose k} (-2)^{k-1} (1+z)^k \; dz \\ = \frac{1}{2} (-1)^{n} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^n} (1+z)^{n-2} (-1-2z)^n \; dz \\ = \frac{1}{2} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^n} (1+z)^{n-2} (1+2z)^n \; dz.$$

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

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

Put $z=2w$ in this integral to get $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{2^n w^n} (1+2w)^{n} (2+2w)^{n-2}\; 2dw \\ = \frac{1}{2} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^n} (1+2w)^{n} (1+w)^{n-2}\; dw.$$

This once more concludes the argument.

• there is no way to derive this without complex analysis? i'm asking because it is in the begining of the book and I expected it to be done with summation and binomial techniques etc – lea Oct 22 '15 at 7:20
• And again a nice application of the residue calculus :-) (+1) – Markus Scheuer Oct 23 '15 at 23:01
• Thank you for your answer. I hope to be able to appreciate it in the future :-) – lea Oct 27 '15 at 19:35