discrete math - binomial coefficients

Question

Show that C(m,0)C(n,k) + C(m,1)C(n,k+1) +...+ C(m,m)C(n,k+m) = C(m+n,n-k).

Answer 1

This looks like a homework question, so rather than prove it for you, here are some approaches which you can take in order to arrive at a proof on your own, and some definitions that may help you along the way.

C(n, k) is typically used to denote the binomial coefficient, which can be defined as C(n,k) = n! / (k! (n - k)!).

The question is asking you to prove a congruence -- that two different equations are equivalent. There are at least two ways to proceed.

One way to do this just to apply algebra and the definition of C(n,k) to manipulate the terms on either side of the equals sign and arrive at identical expressions.

A second way to prove a congruence is using a double-counting argument. This is a proof technique for showing that two expressions are equal by demonstrating that they are two different ways to count the size of the same set. In this instance, we can use the fact that C(n,k) is the number of ways to choose k elements from a set of n elements to analyze the term on the right: C(m+n, n-k). If we can show that the summation on the left is a way to choose n-k elements from a set of m+n elements, we will have obtained a valid proof using this technique.