Proving identities using combinatorial interpretation of binomial coefficients 
Let $n \in \mathbb{N}$. Prove the identities $$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$ and $$\sum^{n}_{k=0}\binom{n}{k}^2 = \binom{2n}{n}$$ by using only the combinatorial interpretation of the binomial coefficient.

I don't exactly get what it means with "combinatorial interpretation of binomial coefficient". I can solve the first identity simply using binomial coefficient like this:
$$\binom{n-1}{k-1} + \binom{n-1}{k} = \frac{(n-1)!}{(n-k)!(k-1)!} + \frac{(n-1)!}{(n-k-1)!k!} = \frac{(n-1)!k}{(n-k)!k!} + \frac{(n-1)!(n-k)}{(n-k)!k!} = \frac{(n-1)![k+(n-k)]}{(n-k)!k!} = \frac{(n-1)!n}{(n-k)!k!} = \frac{n!}{(n-k)!k!} = \binom{n}{k}$$
And for the second identity, I can apply symmetry, then Vandermonde to get:
$$\sum^{n}_{k=0}\binom{n}{k}^2 = \sum^{n}_{k=0}\binom{n}{k}\binom{n}{n-k} = \binom{2n}{n}$$
Though, I don't exactly understand whether the problem asks for this kind of solution, if not, I would like to see a proof to the identities using combinatorial interpretation of binomial coefficient.
 A: "Using a combinatorial interpretation" means using what the symbol $\dbinom{n}{k}$ means; namely, the number of ways of choosing $k$ things from $n$ things. In each case, you want to count the things in two different ways.
Hints:


*

*$\dbinom{n}{k}$ is the number of ways choosing $k$ things from $n$. Divide the $n$ things into a group of $n-1$ and a group of $1$. If you choose $k$ things from the $n$, how many might you have chosen from the first group? From the second?

*Similarly, consider $2n$ things, and divide them into two groups of $n$ things. If you choose $n$ things from those $2n$, then how many will you have chosen from the first group? From the second?

A: I think what they mean is an argument like the following (for the first identity). Let  $X$ be an $n$-element set. Then $\binom{n}{k}$ is the number of $k$-element subsets of $X$. If $x\in X$ is a fixed element of $X$, then I can divide the $k$-element subsets of $X$ into two classes: those which contain $x$ and those that do not. The $k$-element subsets not containing $x$ are precisely the $k$-element subsets of $X-\{x\}$, and there are $\binom{n-1}{k}$ such sets. Then $k$-element subsets of $X$ which do contain $x$ are all of the form $\{x\}\cup Y$, where $Y$ is a $k-1$-element subset of $X-\{x\}$; there are $\binom{n-1}{k-1}$ such sets. Thus, in total, there are $\binom{n-1}{k} + \binom{n-1}{k-1}$ total $k$-element subsets of $X$, proving that $$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.$$
Notice, this was done purely using the interpretation of the binomial coefficients as the number of subsets of a given size of a larger set; we did not use the formula for the binomial coefficients at all. I think this is what they are asking for.
