0
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Omer Jul 17 at 19:35
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.