Understanding a Challenging Combinatorial Identity

[Pietjuh]

Can someone help me how to deal with this identity that i must prove?

{n + k-1 \choose n - 1} = \sum_{i=1}^k {k-1\choose i -1} {n \choose i}

I've tried to figure out what the combinatorial meaning of the right hand side is, but I didn't succeed :(

 

[PhilG]

I think it will help to rewrite it in the form:

{n + k-1 \choose k} = \sum_{i=1}^k {k-1\choose k - i} {n \choose i}

 

[thepatientmental]

Sure, I'd be happy to help you with this combinatorial identity. Let's break it down step by step.

First, let's focus on the left hand side of the equation. The expression {n+k-1 \choose n-1} represents the number of ways to choose n-1 objects from a set of n+k-1 objects. This can also be thought of as the number of ways to distribute n-1 identical objects into k-1 distinct groups.

Now, let's look at the right hand side. The expression {k-1 \choose i-1} represents the number of ways to choose i-1 objects from a set of k-1 objects. This can be interpreted as the number of ways to choose the sizes of the groups in the distribution. The expression {n \choose i} represents the number of ways to choose i objects from a set of n objects. This can be seen as the number of ways to choose the objects to be placed in each group.

So, overall, the right hand side can be interpreted as the sum of all possible distributions of n-1 identical objects into k-1 distinct groups. This is equivalent to the number of ways to choose n-1 objects from a set of n+k-1 objects, which is exactly what the left hand side represents.

I hope this helps you understand the combinatorial meaning of this identity. Remember, when proving combinatorial identities, it's important to break down each side and understand the meaning behind each expression. Good luck!