Using Combinatorial proof to conclude $\binom{2n}{n} = 2 \binom{2n-1}{n-1}$ 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.
 A: 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}$.
A: 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.
