# How to prove this combinatoric identity?

Let m and n be nonnegative integers. Prove that

sum [k=0 to n] (-1)^k * C(m+n+1, m+l+1) * C(m+l, m) = 1.

C(n,k) is the binomial coefficient: n! / (k! * (n-k)!).

I have derived this formula from another problem and thought it could be interesting to have a direct proof. I have not found any yet, so I decided to share this with the community.

Have fun!

Update:

I am sorry for confusion, the l's should be all k, the summation index. I was rewriting this from my notes and renaming the index at the same time. The correct version:

sum [k=0 to n] (-1)^k * C(m+n+1, m+k+1) * C(m+k, m) = 1.

Update 2:

finehalllibrary: I really can't see the straight forward equivalence you have used in the beginning :-/ Could you please explain it a bit more?

Relevance

Pascal's rule: C(n,k) = C(n-1,k) + C(n-1, k-1)

First, show

sum [k=0 to n] (-1)^k * C(m+n+1, m+k+1) * C(m+k, m) = 1

is equivalent to

sum [k=0 to n] (-1)^k * C(m+n, m+k) * C(m+k, m) = 0

using Pascal's rule and induction. (straight forward)

Use the definition of binomial coefficient to rewrite the equation as

(m+n)!/(m!n!) sum [k=0 to n] (-1)^k * (n!/(k!(n-k)!)) = 0

Throw (m+n)!/(m!n!) out the window to get

sum [k=0 to n] (-1)^k * C(n, k) = 0

which again can be shown easily by induction and Pascal's rule.

Edit: I don't see the relevance of m. You might as well just take it out and show

[k=0 to n] (-1)^k * C(n+1, k+1) = 1

Edit:

n = 0

n_0 = C(m+1, m+1) * C(m, m)

n = 1

n_1 = C(m+2, m+1) * C(m, m) - C(m+2, m+2) * C(m+1, m)

= C(m+1, m+1) * C(m, m) + C(m+1, m) * C(m, m) - C(m+2, m+2) * C(m+1, m)

= n_0 + C(m+1, m) * C(m, m) - C(m+2, m+2) * C(m+1, m)

n = 2

n_2 = C(m+3, m+1) * C(m, m) - C(m+3, m+2) * C(m+1, m) + C(m+3, m+3) * C(m+2, m)

=C(m+2, m+1) * C(m, m) + C(m+2, m) * C(m, m) - C(m+2, m+1) * C(m+1, m) - C(m+2, m+2) * C(m+1, m) + C(m+3, m+3) * C(m+2, m)

=n_1 + C(m+2, m) * C(m, m) - C(m+2, m+1) * C(m+1, m) + C(m+3, m+3) * C(m+2, m)

n_(x) = n_(x-1) + sum [k=0 to x] (-1)^k * C(m+x, m+k) * C(m+k, m)

• Sorry I don't have an answer for you, partly because I have been spending too much time on the contest here, http://www.azspcs.net/Contest/PointPacking , which may be of interest to you or others who read this.

Mainly, I am replying to call your attention to a free book which you can download, and whose title is simply "A=B". This book is devoted to showing how to prove combinatorial identities such as the one in your question. It shows how actual proofs can be obtained using Maple, which I believe you have. The book, by Doron Zeilberger et al can be downloaded from this site:

http://www.math.upenn.edu/~wilf/AeqB.html

At the same site is a maple package called EKHAD whose purpose is to prove combinatorial identities. I hope these will be of interest to you.