Partial sum of alternating series involving binomials

Question

I ran across an interesting expression that I cannot prove (but tested numerically):

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

for any $0 \leq i < n$.

In fact I cannot even prove the case with $i = 0$ -- Wolfram alpha knows it is true somehow, but gives no hints.

I looked at at the identities involving binomials at wikipedia and mathworld. The closest identity that I found was Dixon's identity but I failed to rewrite the problem in to apply it. Rewriting the problem with the usual binomial identities (binomial complement, etc.) seems to get nowhere or least the strategy is unclear to me. By using the definition of binomial and rewriting in factorials did not work either.

I am not sure how to approach this kind of proof, any suggestions?

Answer 1

I will first try to explain why the result is true in the $i=0$ case. Write it as $$ 1 = \sum_{j=1}^{n} (-1)^{j-1} \binom{n}{n-j} \binom{n+j-1}{j} $$ which is $$ 0 = \sum_{j=0}^{n} (-1)^{j} \binom{n}{n-j} \binom{n+j-1}{j}. $$ Then suppose you have to put $n$ balls in $n$ boxes. For $j$ = $0$ to $n$, let there be $j$ red balls and $n-j$ blue balls. The first binomial factor in each term $\displaystyle\binom{n}{n-j}$ is the number of ways of putting one blue ball in each of $n-j$ boxes, and the second, $\displaystyle \binom{n+j-1}{j}$, is the number of ways of putting $j$ red balls in the $n$ boxes, with as many in each box as you like.

Now consider an arrangement of the balls in the boxes with exactly $k$ of the boxes used. This can only happen in the cases where $n-j$ is at most $k$, so suppose $j=n-k+r$, where $r=0\ldots k$. Then we count this arrangement $\displaystyle \binom{k}{r}$ ways (the number of ways of choosing which of the $k$ boxes doesn't have a blue ball in). But now, in the whole sum, we count how many times this arrangement appears: this is the alternating sum of a whole row of Pascal's triangle, so zero.

An algebraic version of the argument above is as follows. $$ \binom{n}{n-r} \binom{n-1}{r} \binom{n-r}{n-j} = \binom{n}{n-j} \binom{j}{r} \binom{n-1}{r} $$ (just by rearranging the factorials), so $$ \sum_{r=0}^j\binom{n}{n-r} \binom{n-1}{r} \binom{n-r}{n-j} = \binom{n}{n-j}\sum_{r=0}^j \binom{j}{j-r} \binom{n-1}{r}=\binom{n}{n-j} \binom{n+j-1}{j} $$ Now insert this in the sum above. $$ \sum_{j=0}^{n} (-1)^{j} \binom{n}{n-j} \binom{n+j-1}{j}=\sum_{j=0}^{n} (-1)^{j}\sum_{r=0}^j\binom{n}{n-r} \binom{n-1}{r} \binom{n-r}{n-j} $$ Interchanging the order of the sums, gives $$ \sum_{r=0}^{n}\binom{n}{n-r} \binom{n-1}{r} \sum_{j=r}^n (-1)^{j}\binom{n-r}{n-j}=0 $$ because the sum over $j$ is zero.

Now all you have to do is extend to $i \neq 0$!

Answer 2

We seek to show that with $0\le q\lt n$

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

We see that $p=n$ does not really contribute owing to the first binomial coefficient. We write

$$[z^{n-1}] (1+z)^{n+q} \sum_{p\ge 0} (-1)^p z^p {n+p\choose n-q-1} {p+q\choose q}.$$

Here we have extended to infinity due to the coefficient extractor. Continuing,

$$[z^{n-1}] (1+z)^{n+q} [w^{n-1-q}] (1+w)^n \sum_{p\ge 0} (-1)^p z^p (1+w)^p {p+q\choose q} \\ = [z^{n-1}] (1+z)^{n+q} [w^{n-1-q}] (1+w)^n \frac{1}{(1+z(1+w))^{q+1}} \\ = [z^{n-1}] (1+z)^{n-1} [w^{n-1-q}] (1+w)^n \frac{1}{(1+zw/(1+z))^{q+1}} \\ = [z^{n-1}] (1+z)^{n-1} [w^{n-1-q}] (1+w)^n \sum_{p=0}^{n-1} {p+q\choose q} (-1)^p w^p \frac{z^p}{(1+z)^p}.$$

The upper limit on this sum is due to the factor $z^p$ and the coefficient extractor in $z.$ Note that ${n-1-p\choose n-1-p} = 1$ so this becomes

$$[w^{n-1-q}] (1+w)^n \sum_{p=0}^{n-1} {p+q\choose q} (-1)^p w^p.$$

At this point we are now permitted to raise to infinity again, this time due to the coefficient extractor in $w$:

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

This is the claim. Note that we have used the condition $0\le q\lt n$ in the coefficient extractor on $w.$