Partial sum of alternating series involving binomials

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?

• Please see this article on MathSE protocol. As onerous as the article may appear to you, it provides a defense mechanism against the MathSE forum being used as a do my homework forum. In particular, please see the Edit-Tools section of the article, and the portion of the article that discusses showing work. It is irrelevant whether the problem is homework. What counts is whether the protocol is observed. Commented Mar 11, 2023 at 23:02
• The summation variable is usually only specified in the lower limit of the sum, not in the upper limit. Commented Mar 12, 2023 at 10:45
• How did you come up with this identity? You must have had reason to believe it holds before you tested it numerically? Commented Mar 12, 2023 at 10:46
• @joriki It is a long story - I was looking at series expansion using Galerkin principle and proving that it is able to derive the Taylor series... a lot of steps along the way, this is the last piece of the puzzle left to prove. Commented Mar 12, 2023 at 10:54

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

• +1 : I like your answer. I recommend that if the question is ever deleted, that you personally create a separate self-answer question, and post this as your answer to your own question. If there are particular sources on Combinatorics theory (i.e. books, pdf-s) that helped educate you in studying Combinatorics, you might include links to the corresponding references in your answer. Commented Mar 12, 2023 at 14:47
• @mcd nice! Thanks for the answer. It is an interesting concept adding the additional sum and exchanging sums. Also, your insight in the beginning of the answer makes the answer superb. I am satisfied and I am not going to delete the question. Commented Mar 12, 2023 at 17:51

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

• Great derivation! (+1) Commented Mar 12, 2023 at 22:24