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

Question

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 1

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.

Answer 2

The right side of your equation equals $\binom{3n+1}{2n+1}$, the number of $(2n+1)$-element subsets $X$ of $\{0,1,2,\dots,3n\}$. Classify these $X$'s according to their first element $k$, which must be one of $0,1,\dots,n$; it can't be bigger than $n$ because there are $2n$ elements larger than it in $X$.

Now for any fixed $k$, the number of $X$'s whose first element is that particular $k$ is the number of ways to choose the remaining $2n$ elements of $X$ from $k+1,k+2,\dots,3n$. That is, it's the number of ways to choose $2n$ elements out of $3n-k$ elements, i.e., $\binom{3n-k}{2n}$.

Finally, un-fixing $k$, we get that the total number of possible $X$'s is $\sum_{k=0}^n\binom{3n-k}{2n}$, the left side of your equation.

Answer 3

If you reverse the order of summation to rewrite as $$\sum_{m=2n}^{3n} \binom{m}{2n} = \binom{3n+1}{2n+1},$$ this is a special case of Identity 135 in Proofs that Really Count: The Art of Combinatorial Proof: $$\sum_{m=k}^{n} \binom{m}{k} = \binom{n+1}{k+1}.$$ The book uses the subset-counting approach, conditioning on the largest element $m+1$ in the subset.

Answer 4

You could use the fact that: $$\sum_{k=0}^n\begin{pmatrix}3n-k\\2n\end{pmatrix}=\frac{1}{(2n)!}\sum_{k=0}^n\frac{(3n-k)!}{(n-k)!}=\frac{(3n)!}{(2n)!n!}\sum_{k=0}^n\prod_{i=1}^k\left(\frac{n-i}{3n-i}\right)$$ and maybe there is a way of simplifying using the fact that: $$\frac{n-i}{3n-i}=\frac 13\left(1-\frac{2i}{3n-i}\right)$$