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

Question

Let $n$ be a positive integer and fix a non-negative integer $j\le n-1$. Is it true that $$ \sum_{i=j}^{n-1}\binom{n}{i}\binom{i}{j}(-1)^i=\binom{n}{j}(-1)^{n-1} $$ or, equivalently, $$ \sum_{i=0}^{n-1-j}\binom{n}{i+j}\binom{i+j}{j}(-1)^i=\binom{n}{j}(-1)^{n+j+1}\,\,\,? $$

[This is only a conjecture]

have you used Wolfram to do some caculations to check if it is true? — runaround, Feb 26 '16 at 22:50
You probably want to include the first summation, before the edit, too, since that one was a little easier to read — , Feb 26 '16 at 22:51
It is true, according to Mathematica, so you can replace "conjecture" with "theorem". — Patrick Stevens, Feb 26 '16 at 22:53
Hint; $${n\choose i+j}{i+j\choose j} = {n\choose j}{n-j\choose i}$$ and you may move the first binomial coefficient to the front. — Marko Riedel, Feb 26 '16 at 22:54
Thanks Patrick; I was almost sure of that, but at the moment I am not able to prove it.. — , Feb 26 '16 at 22:54
Ahhhhhhhh Marko that's the usual trick of the papers of Zhi-Wei Sun! Thanks again, now it is clear how to conclude — , Feb 26 '16 at 22:57

score 3 · Accepted Answer · answered Feb 26 '16 at 22:57

3

First note that your conjecture is equivalent to

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

Now

$$\binom{n}i\binom{i}j=\binom{n}j\binom{n-j}{i-j}\;,$$

so $(1)$ can be rewritten as

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

which is equivalent to

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

Letting $k=i-j$, we can rewrite $(2)$ as

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

which, after multiplication by $(-1)^j$, becomes

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

This is just a special case of the binomial theorem, specifically, for $(-1+1)^{n-j}$, which we know is $0$ unless $n=j$, in which case it’s $1$. Thus, your conjecture is true provided that $n>j$.

answered Feb 26 '16 at 22:57

Brian M. Scott

616,228

(+1). Did you see my comment? – Marko Riedel Feb 26 '16 at 23:01
@Marko: Not until just now: you must have commented while I was writing. – Brian M. Scott Feb 26 '16 at 23:03
Considering the lenght and the timing, indeed, not :P – Feb 26 '16 at 23:03

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

1 Answers1