8
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Nice argument! But the fractions don't really work when $k < j$; it is better to argue $\dbinom{n}{k}\dbinom{k}{j} = \dbinom{n}{j}\dbinom{n-j}{n-k}$ using the $\dbinom{a}{b} = \dfrac{1}{b!} a\left(a-1\right)\cdot\left(a-b+1\right)$ formula. $\endgroup$ – darij grinberg Jun 19 '15 at 23:09
  • $\begingroup$ @darijgrinberg: True. I used, without stating so, the convention that $1/r!=0$ when $r$ is a negative integer: alternatively, specifying that $j\le k$. Will add a comment to that effect in the answer. $\endgroup$ – Einar Rødland Jun 19 '15 at 23:15
  • $\begingroup$ @Einar Rødland, Thank you for your nice answer. $\endgroup$ – Ji-Cai Liu Jun 20 '15 at 2:27
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice proof! Your indices are messed up in the last equality (the $\ell$ on the LHS is a running index, while that on the RHS should probably be $m$). $\endgroup$ – darij grinberg Jun 19 '15 at 23:17
  • $\begingroup$ @darij: You’re absolutely right; thanks for catching that! $\endgroup$ – Brian M. Scott Jun 19 '15 at 23:23
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

First let's check, if \begin{align*} \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}\tag{1} \end{align*} is a Saalschütz identity.

According to $A=B$ section 3.5, the Saalschütz identity has the general representation as the hypergeometric series \begin{align*} _{3}F_{2}\left(a,b,c;d,e;1\right)=\sum_{k=0}^{\infty}\frac{(a)_k(b)_k(c)_k}{(d)_k(e)_k} \end{align*} with $a+b+c+1=d+e$ and $c$ a negative integer.

Note, that $(x)_k=x(x-1)\cdot\ldots\cdot (x-k+1)$ is the Pochhammer symbol.

Since \begin{align*} a_k&=(-1)^k\binom{n}{k}\binom{n+k}{k}\binom{k}{j}\\ &=(-1)^k\frac{(n+k)!}{k!(n-k)!(k-j)!j!} \end{align*} The quotient $\frac{a_{k+1}}{a_k}$ is \begin{align*} \frac{a_{k+1}}{a_k}=\frac{(k+1)^2(k+1-j)}{(k-n)(k+n+1)}\cdot\frac{1}{k+1} \end{align*} which gives $$_{3}F_{2}\left(1,1,1-j;-n,n+1;1\right)$$ We observe \begin{align*} a+b+c+1&=4-j\\ d+e&=1 \end{align*} and conclude, if my calculation is correct the binomial identity is a Saalschütz identity only in case $j=3$.

Proof of the binomial identity

We use Egorychevs formal residual calculus for power series.

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*} \sum_{k=0}^{\infty}&(-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}}\\ &=(-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)$$

$\endgroup$
  • $\begingroup$ Please do read my answer. It is exactly the same as yours, and I was first. The summation is the same as are the functions involved. From the point of view of didactics yours is the better answer. $\endgroup$ – Marko Riedel Jun 19 '15 at 21:58
  • $\begingroup$ If I read this correctly your factor of $(-1)^n$ shows up one line too soon and the expansion of the term $1-(1+u)(1+t)$ is incorrrect and the power on $u$ on line seven is off by one. $\endgroup$ – Marko Riedel Jun 19 '15 at 22:07
  • $\begingroup$ @MarkoRiedel: I see and you're right. I've added a comment regarding the same techniques. Thanks for your nice statement regarding didactics. Nevertheless +1 for your answer of course. And you're right: Together with Jack D'Aurizios and Brian Scotts answer we have a broad spectrum of different approaches. :-) $\endgroup$ – Markus Scheuer Jun 19 '15 at 22:09
  • $\begingroup$ I apologize for the tone. I use the Egorychev method a lot and in fact I learned the name from one of your posts and I do mention it if I remember. Of course this is really the Cauchy Residue Theorem in disguise. I used the method on an unanswered question that I put a bounty on an hour ago. $\endgroup$ – Marko Riedel Jun 19 '15 at 22:13
  • $\begingroup$ @MarkoRiedel: Don't worry! I appreciate it if typos or errors can be fixed. $\endgroup$ – Markus Scheuer Jun 19 '15 at 22:24

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.