Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
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
1  
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
add comment

1 Answer

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

share|improve this answer
    
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.