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?

2 Answers

Relevance
  • farful
    Lv 4
    1 decade ago
    Favorite Answer

    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)

  • JB
    Lv 7
    1 decade ago

    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.

Still have questions? Get your answers by asking now.