combinatorics - Combinatorial proof of $sum_{k=0}^{n} binom{3n-k}{2n} = binom{3n+1}{n}$

I had an exercise to prove the following equation:

$$\sum_{k=0}^{n} \binom{3n-k}{2n}= \binom{3n+1}{n}$$ I was able to prove it using Pascal's Identity a lot of times, but I'm wondering if there is a combinatorial proof of this. Anyone has an idea for a combinatorial proof?

Answer

We can use the method of committee-forming.

Consider a group of $3n + 1$ people, such that we want to choose a committee of $n$ people from that group. Note $\sum_{k=0}^{n} \binom{3n-k}{2n} = \sum_{k=0}^{n} \binom{3n-k}{n-k} = \binom{3n}{n} + \binom{3n-1}{n-1} + ... + \binom{2n}{0}$. Select one person. We can either choose for him to not be in the group with $\binom{3n}{n}$ ways to do so, or be in the group. Assume he is in the group. Next, select a different person. If he is not in the group, we have $\binom{3n-1}{n-1}$ ways to choose the committee from the other $3n-1$ members, and now assume he is in the group, etc.

Alternatively, consider a list of $3n+1$ numbers, such that you want to remove $2n+1$ of them. Consider the largest number that you remove - if it is $3n+1$, there are $\binom{3n}{2n}$ ways to remove the rest; if it is $3n$, there are $\binom{3n-1}{2n}$ ways to remove the rest; etc.