# 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
• farful
Lv 4

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