# 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?

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.

• Nice, but I think this is actually what I did as your proof really looks like the proof of Pascal's Identity done a lot of times. I'll accept that anyways if no one has something else. Thanks for your answer!
– Omer
Commented Jul 17, 2019 at 19:35

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.

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.

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)$$