# An enlightening proof of a specific combinatorial identity

Concerns about the arithmetic genus of projective hypersurfaces led me to make the following combinatorial conjecture: $${d-1\choose n+1} =\sum_{i=0}^{n+1} (-1)^{n+i+1} {d\choose i}$$ for $d \geq 1$, $n \geq 0$. If I made no mistakes in my code, I was also able to find some reasonably strong numerical evidence that this is, in fact, an identity. Unfortunately, my skill at combinatorics is sufficiently poor that while I might be able to prove the statement with a fair amount of effort, I doubt I could find an enlightening proof.

Can someone supply an enlightening proof of the statement above?

Obviously, a counterexample would also suffice, but I doubt there is one.

Additional note: I did not see a reasonable way to search for this specific identity, so it is quite possible this is an exact duplicate of another question, in which case my question should be closed.

-
Looks very similar to equations 11 & 12: $$\sum_{j=0}^k(-1)^j{n\choose j}=(-1)^k{n-1\choose k}$$ which is said to hold for all $n\ne0$. – bgins Apr 10 '12 at 22:47
@bgins: I think it is in fact the same identity, with my $d$ corresponding to $n$ and my $n$ corresponding to $k-1$. Unfortunately, the suggested proof is "by induction." But it is very helpful to know this is, in fact, a standard identity. – Charles Staats Apr 10 '12 at 22:54
Note that they go on to say it's a special case of a theorem about finite differences of a polynomial (equation 12): $$\deg P(x)\le n\implies\sum_{j=0}^n(-1)^j{n\choose j}P(j)=0$$ This is certainly a standard theorem. – bgins Apr 10 '12 at 22:58
It think you should use ${n \choose k}={{n-1} \choose k}+{{n-1} \choose {k-1}}$ to telescope. – Pedro Tamaroff Apr 10 '12 at 23:09

Let’s replace $n+1$ by $n$ in order to simplify the notation; the conjectured identity then becomes

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

Suppose first that $d\le n$. Clearly $\dbinom{d-1}n=0$, and

$$\sum_{i=0}^n(-1)^i\binom{d}i=\sum_{i=0}^d(-1)^i\binom{d}i=(1-1)^d=0$$ by the binomial theorem, since $d\ge 1$.

Now suppose that $1\le n<d$. Then

\begin{align*} \sum_{i=0}^n(-1)^i\binom{d}i&=\sum_{i=0}^n(-1)^i\left(\binom{d-1}i+\binom{d-1}{i-1}\right)\\ &=\sum_{i=0}^n(-1)^i\binom{d-1}i+\sum_{i=1}^n(-1)^i\binom{d-1}{i-1}\\ &=\sum_{i=0}^n(-1)^i\binom{d-1}i+\sum_{i=0}^{n-1}(-1)^{i+1}\binom{d-1}i\\ &=\sum_{i=0}^n(-1)^i\binom{d-1}i-\sum_{i=0}^{n-1}(-1)^i\binom{d-1}i\\ &=(-1)^n\binom{d-1}n\;, \end{align*}

and the identity follows immediately by multiplying by $(-1)^n$.

-
@Brain I had this in mind, but since I never deal with this type of problems, I flinched! – Pedro Tamaroff Apr 10 '12 at 23:12