Partial sum of alternating series involving binomials

binomial-coefficientscombinatoricssummation

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?

Best Answer

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$!

Related Question