Is this combinatorial identity a special case of Saalschutz's theroem?

Question

When I solved a question, the following combinatorial identity was used $$ \sum_{k=0}^{n}(-1)^k{n\choose k}{n+k\choose k}{k\choose j}=(-1)^n{n\choose j}{n+j\choose j}. $$ But to prove this identity is difficulty for me. I think it may be a special case of the Saalschutz's theroem, wchich is stated as follows $$ \sum_{k=0}^{n}\frac{(-n)_k(a)_k(b)_k}{(1)_k(c)_k(1+a+b-c-n)_k}=\frac{(c-a)_n(c-b)_n}{(c)_n(c-a-b)_n}, $$ where $(a)_k=a\cdot (a+1)\cdots (a+k-1)$. If it isn't the special case of Saalschutz's theroem, can you present a proof of this identity? All hints, proofs and references are welcome.

Answer 1

Multiply the desired identity by $(-1)^n$ to get

$$\sum_{k=0}^{n}(-1)^{n-k}\binom{n}k\binom{n+k}k\binom{k}j=\binom{n}j\binom{n+j}j\;,$$

and rewrite it as

$$\sum_{k=0}^n(-1)^k\binom{n}k\binom{2n-k}{n-k}\binom{n-k}j=\binom{n}j\binom{n+j}n\;.\tag{1}$$

We may assume that $j\le n$. You have $2n$ white balls numbered from $1$ through $2n$. The righthand side of $(1)$ is the number of ways to pick $j$ of the balls from the balls with numbers $1$ through $n$, dump those in a box with the balls numbered $n+1$ through $2n$, and then choose $n$ of the balls in the box and paint them red.

Alternatively, there are $\binom{2n}n\binom{n}j$ ways to choose any $j$ of the balls numbered $1$ through $n$, dump them in a box with the balls numbered $n+1$ through $2n$, and then choose any $n$ of the $2n$ balls to paint red, regardless of whether or not the balls are in the box. Of course some of these outcomes result in red balls not in the box, and we want to exclude those.

For $k=1,\ldots,n$ let $B_k$ be the set of outcomes in which ball $k$ ends up red but not in the box. There are $\binom{2n-1}{n-1}$ ways to choose the other $n-1$ red balls, and there are $\binom{n-1}j$ ways to choose $j$ balls from the first $n$, not including ball $k$, to go into the box. Thus,

$$|B_k|=\binom{2n-1}{n-1}\binom{n-1}j\;.$$

Similarly, if $1\le k<\ell\le n$,

$$|B_k\cap B_\ell|=\binom{2n-2}{n-2}\binom{n-2}j\;,$$

and in general for $1\le k_1<k_2<\ldots k_m\le n$ we have

$$\left|\bigcap_{\ell=1}^mB_{k_\ell}\right|=\binom{2n-m}{n-m}\binom{n-m}j\;,$$

and we see that $(1)$ is just an application of the inclusion-exclusion principle.

Answer 2

The result is more easily proved without the use of Saalschutz' theorem.

A good starting point for evaluating such sums may be to write them out in terms of factorials: $$ (-1)^k \binom{n}{k}\binom{n+k}{k}\binom{k}{j} =\frac{(-1)^k\,n!\,(n+k)!\,k!}{k!\,(n-k)!\,k!\,n!\,j!\,(k-j)!} =\frac{(-1)^k\,(n+k)!}{k!\,(n-k)!\,j!\,(k-j)!} $$ for $j\le k\le n$ (otherwise the LHS is zero). I often think of the sum as over all $k\in\mathbb{Z}$, but with the convention that $1/r!=0$ when $r$ is a negative integer.

You may note that $k$ appears in four of the factorials. This means we can try to rewrite the expression so that we may use the rule $$ \sum_k\binom{a}{p+k}\binom{b}{q-k}=\binom{a+b}{p+q} $$ where $a$ or $b$ may be negative using the conversion $$ \binom{-(m+1)}{k} =(-1)^k\binom{m+k}{k} =(-1)^k\binom{m+k}{m}. $$ We may do so as $$ \frac{(-1)^k\,(n+k)!}{k!\,(n-k)!\,j!\,(k-j)!} =(-1)^k\binom{n+k}{k}\binom{n-j}{n-k}\binom{n}{j} =\binom{-(n+1)}{k}\binom{n-j}{n-k}\binom{n}{j} $$ which gives us the sum $$ \sum_k\binom{-(n+1)}{k}\binom{n-j}{n-k}\binom{n}{j} =\binom{-(j+1)}{n}\binom{n}{j} =(-1)^n\binom{n+j}{j}\binom{n}{j}. $$

---

As Darij pointed out, the result could be obtain a little more directly (without writing out all the factorials) by using $$ \binom{n}{k}\binom{k}{j}=\binom{n}{j}\binom{n-j}{n-k}. $$ Of course, since I never remember these kinds of rules, I personally have to write this out as factorials anyway, but doing so only for these two binomials is a bit simpler than doing it for all three (and more so in more complicated cases).

Answer 3

The LHS is the coefficient of $x^j$ in: $$ \sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{n+k}{k}(1+x)^k $$ hence we just need to find: $$ \sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{n+k}{k}z^k =\phantom{}_2 F_1(-n,1+n,1,z)=P_n^{(0,0)}(1-2z)$$ that is a Jacobi polynomial, better known as the shifted Legendre polynomial $\tilde{P}_n(z)$.

Then your claim just follows from the Rodrigues' formula.

Answer 4

Remark. Incorporates a correction by Markus Scheuer.

Suppose we seek to evaluate

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

which is claimed to be $$(-1)^n {n\choose j}{n+j\choose j}.$$

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

and $${k\choose j} = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{k}}{w^{j+1}} \; dw.$$

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

This is $$\frac{(-1)^n}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n}}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{j+1}} \sum_{q=0}^n {n\choose q} w^q (1+z)^q \; dw \; dz.$$

Extracting the residue at $w=0$ we get $$\frac{(-1)^n}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n}}{z^{n+1}} {n\choose j} (1+z)^j \; dz \\ = {n\choose j} \frac{(-1)^n}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n+j}}{z^{n+1}}\; dz \\ = (-1)^n {n\choose j} {n+j\choose n}.$$

thus proving the claim.

Answer 5

Here's another variation of the theme (similar to the techniques presented in Marko Riedel's answer).

Note: This powerful technique is based upon the Cauchys residue theorem and was introduced by G.P. Egorychev (Integral Representation and the Computation of Combinatorial Sums) to compute binomial identies.

We use only two aspects of this theory. Let $A(z)=\sum_{j=0}^{\infty}a_jz^j$ be a formal power series, then

• Write the binomial coeffients as residuals of corresponding formal power series

\begin{align*} \mathop{res}_{z}\frac{A(z)}{z^{j+1}}=a_j\tag{1} \end{align*}

• Apply the substitution rule for formal power series:

\begin{align*} A(z)=\sum_{j=0}^{\infty}a_jz^{j}=\sum_{j=0}^{\infty}z^j\mathop{res}_{w}\frac{A(w)}{w^{j+1}}\tag{2} \end{align*}

We observe:

\begin{align*} \color{blue}{\sum_{k=0}^{\infty}}&\color{blue}{(-1)^k{n\choose k}{n+k\choose k}{k\choose j}}\tag{3}\\ &=\sum_{k=0}^{\infty}(-1)^k\mathop{res}_{z}\frac{(1+z)^n}{z^{k+1}} \mathop{res}_{u}\frac{(1+u)^{n+k}}{u^{k+1}} \mathop{res}_{t}\frac{(1+t)^{k}}{t^{j+1}}\tag{4}\\ &=\mathop{res}_{u,t}\frac{(1+u)^n}{ut^{j+1}}\sum_{k=0}^{\infty}\left((-1)\frac{(1+u)(1+t)}{u}\right)^k \mathop{res}_{z}\frac{(1+z)^n}{z^{k+1}}\tag{5}\\ &=\mathop{res}_{u,t}\frac{(1+u)^n}{ut^{j+1}}\left(1-\frac{(1+u)(1+t)}{u}\right)^n\tag{6}\\ &=(-1)^n\mathop{res}_{u,t}\frac{(1+u)^{n}}{u^{n+1}t^{j+1}}\left(1+(1+u)t\right)^n\\ &=(-1)^n\mathop{res}_{u}\frac{(1+u)^{n}}{u^{n+1}}[t^j]\sum_{k=0}^n\binom{n}{k}(1+u)^kt^k\tag{7}\\ &=(-1)^n\mathop{res}_{u}\frac{(1+u)^{n}}{u^{n+1}}\binom{n}{j}(1+u)^j\\ &=(-1)^n\binom{n}{j}\mathop{res}_{u}\frac{(1+u)^{n+j}}{u^{n+1}}\\ &\,\,\color{blue}{=(-1)^n\binom{n}{j}\binom{n+j}{n}} \end{align*}

Comment:

• In (3) we change the limit to $\infty$ without changing the value, since we add only $0$.

• In (4) we use $(1+z)^n$ as formal power series with the coefficients $\binom{n}{k}$ according to (1) and similarly for expressions in $u$ and $t$

• In (5) we do some rearrangement to prepare the application of the substitution rule

• In (6) we apply the substitution rule according to (2)

• In (7) we use the coefficient of operator $[t^j]$ to denote the coefficient of $t_j$ in the sum. Observe that following is valid when using the formal residual operator $\mathop{res}$

$$\mathop{res}_t\frac{A(t)}{t^{j+1}}=[t^{-1}]t^{-j-1}A(t)=[t^j]A(t)$$

Answer 6

Here is a derivation using hypergeometric functions. We will see, OP's binomial identity is not a hypergeometric $_3F_2$ function which is subject to the Saalschütz identity, but a hypergeometric $_2F_1$ function instead, which follows another nice identity.

Here we use the rising factorials notation $(a)_{k}:=a(a+1)\cdots(a+k-1)$.

Assuming $n>j$ we obtain \begin{align*} \color{blue}{\sum_{k=j}^n}&\color{blue}{(-1)^k\binom{n}{k}\binom{n+k}{k}\binom{k}{j}}\\ &=\sum_{k=0}^{n-j}\underbrace{(-1)^{k+j}\binom{n}{k+j}\binom{n+k+j}{k+j}\binom{k+j}{j}}_{=:t_k}\\ &=\sum_{k=0}^{n-j}t_k=t_0\sum_{k=0}^{n-j}\prod_{q=0}^{k-1}\frac{t_{q+1}}{t_q}\\ &=(-1)^j\binom{n}{j}\binom{n+j}{j}\\ &\qquad\cdot\sum_{k=0}^{n-j}\prod_{q=0}^{k-1} (-1)^{q+1+j}\binom{n}{q+1+j}\binom{n+q+1+j}{q+1+j}\binom{q+1+j}{j}\\ &\qquad\qquad\qquad\qquad\cdot(-1)^{-q-j} \binom{n}{q+j}^{-1}\binom{n+q+j}{q+j}^{-1}\binom{q+j}{j}^{-1}\\ &=(-1)^j\binom{n}{j}\binom{n+j}{j}\sum_{k=0}^{n-j}\prod_{q=0}^{k-1} \frac{\left(j-n+q\right)\left(j+n+q+1\right)}{\left(q+1\right)\left(j+q+1\right)}\\ &=(-1)^j\binom{n}{j}\binom{n+j}{j}\sum_{k=0}^{n-j}\frac{(j-n)_k(j+n+1)_k}{(j+1)_k}\,\frac{1}{k!}\\ &=(-1)^j\binom{n}{j}\binom{n+j}{j}{_2F_1}\left(j-n,j+n+1;j+1;1\right)\tag{1}\\ &\,\,\color{blue}{=(-1)^n\binom{n}{j}\binom{n+j}{j}}\tag{2} \end{align*} and the claim follows.

Comment:

• In (1) we write the sum as hypergeometric $_2F_1$ function evaluated at $z=1$ with parameter $j-n$ a negative integer.

• In (2) we recall the Chu-Vandermonde identity (see e.g. Corollary 2.2.3 in Special Functions by G.E. Andrews, R. Askey and R. Roy) which is \begin{align*} {_2F_1}(-n,a;c;1)=\frac{(c-a)_n}{(c)_n} \end{align*} We derive from (1) \begin{align*} {_2F_1}(j-n,j+n+1;j+1;1)&=\frac{(-n)_{n-j}}{(j+1)_{n-j}}\\ &=\frac{(-n)(-n+1)\cdots(-j-1)}{(j+1)(j+2)\cdots (n)}\\ &=(-1)^{n-j} \end{align*}