Using Combinatorial proof to conclude $\binom{2n}{n} = 2 \binom{2n-1}{n-1}$

Question

The question given states: Let x be an element of a set A of size 2n. Among the n-element subsets of A count those containing x and those omitting x. Conclude that

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

So i began like this

So the left hand side has been changed to give the equation $$ \sum_{k=0}^nk\binom nk^2 = n\binom{2n-1}{n-1}. $$ replace one factor $\binom nk$ by the equivalent $\binom n{n-k}$, to give as equation to prove $$ \sum_{k=0}^nk\binom nk\binom n{n-k} = n\binom{2n-1}{n-1}. $$

Then I was told you are not allowed to solve it Using induction, so now I'm confused on how to go about this question.

Answer 1

I have $2n$ different doughnuts, including one made of pure chocolate. I want to choose $n$ doughnuts for a healthy breakfast, saving the rest for lunch. There are $\binom{2n}{n}$ ways to do it. Let us count another way.

(i) For breakfast, I could include the one made of chocolate. Then I would need to choose $n-1$ doughnuts from the remaining $2n-1$. This can be done in $\binom{2n-1}{n-1}$ ways.

(ii) Or else I could save the pure chocolate doughnut for lunch. Then I would need to choose $n$ from the remaining $2n-1$. This can be done in $\binom{2n-1}{n}$ ways. But this is $\binom{2n-1}{n-1}$.

It now follows that $\binom{2n}{n}=2\binom{2n-1}{n-1}$.

Remark: One might object that we have used the relation $\binom{2n-1}{n}=\binom{2n-1}{n-1}$ without giving a combinatorial argument.

We could do it like this. The number of ways to choose $n$ doughnuts for breakfast, not including the chocolate one, is precisely the number of ways to save $n$ doughnuts for lunch, including the chocolate one. We already saw that this is $\binom{2n-1}{n-1}$.

Answer 2

In a grid, the number of ways to go from the origin to the point $(n,k)$ —in the first quadrant—, using only the steps $(0,1)$ and $(1,0)$ is given by the binomial coefficient $$\binom{n+k}{k},$$ or the same, $\binom{n+k}{n}$. For reference, I recommend 'Principles And Techniques In Combinatorics' (Chen & Koh).

$\binom{2n}{n}$ counts the number of paths from the origin to $(n,n)$, and the last step of these must come from $(n-1,n)$ or $(n,n-1)$. Then $$\binom{2n}{n}=\binom{n-1+n}{n}+\binom{n+n-1}{n-1}=2\binom{2n-1}{n-1},$$ as desired.