Combinatorial Proof - $\ {1 \over n+1} {2n\choose n} = {2n-1\choose n-1} - {2n-1\choose n+1} = {2n\choose n} - {2n\choose n-1}$

Question

I'm been struggling with this proof for quite a while now - I'm trying to combinatorially prove this expression:

$$ {1 \over n+1} {2n\choose n} = {2n-1\choose n-1} - {2n-1\choose n+1}$$

$$= {2n\choose n} - {2n\choose n-1}$$

Any help would be much appreciated!

Thanks

Answer 1

The answer is easier to see in the form:

$$\binom{2n}{n}=(n+1)\binom{2n}{n}-(n+1)\binom{2n}{n-1}$$

We're going to be counting the number of ways to choose $n$ elements from $2n$, without "marking" any, as you will see in the next section. The left side clearly counts this.

On the right side, we go by complement. Our larger set we count is the set of ways to choose n elements from $2n$ where at most 1 is "marked". We do this by choosing $n$ elements, then either marking one of the $n$ or none ($n+1$ choices).

Now, all we need to subtract are the number of ways to choose $n$ elements and mark exactly one. First, choose $n-1$ unmarked elements, then from the remaining $n+1$, choose an element to mark and put in the set.

By counting by complement, we have counted the number of ways to choose $n$ unmarked elements, concluding the proof.

EDIT: Then we just divide both sides by $n+1$, now concluding the proof.