# 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.

## 2 Answers

"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:

1. $\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?
2. 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?
• I see that @froggie below has given an example for the first identity. Second one involves a sum and square, so it confuses me. If we divide $2n$ into two sets of $n$ and we choose $n$ elements, we can choose all the elements from the first set or second set. This is one option. Another option is that we choose some elements from the first set, and some elements from the second set. Where we can again choose half from first and second, or not, meaning more from one set and less from the other. I guess this corresponds to the sum in the identity, but I have a hard time to formalize a solution. – user72151 Nov 11 '15 at 10:47
• You are on the right track. Suppose you choose $k$ of the elements from the first set. How many then will you choose from the second? So together there are $\binom{n}{k}\binom{n}{n-k} = \binom{n}{k}^2$ ways of choosing $2k$ elements where $k$ of them come from the first set. Can you finish it from there? – rogerl Nov 11 '15 at 13:14
• So, if I choose $k$ elements from the first set, then I need to choose $n-k$ elements from the second set, in order to have chosen $n$ elements. You have already showed this, using the symmetry of binomial coefficient, you have got $\binom{n}{k}^2$. Now, I need to include the summation somehow. I guess this is the part, where we go our all the combinations, like choosing 1 element from the first set, and $n-1$ elements from the second, 2 elements from the first, and $n-2$ elements from the second, and so on and so on. Though, I still don't know how I will write it concretely as a proof. – user72151 Nov 11 '15 at 13:52
• @rogerl Yes, I also got the same part, and I'm also having trouble finalizing the proof for the second part. What do you say about the above comment, and how should it be finalized? – user72151 Nov 11 '15 at 16:15
• Well, I think it's pretty much done using the above comment. Something like: for each $k$, choose $k$ from the first group; then you must choose $n-k$ from the second, giving $\binom{n}{k}^2$. Summing over all possible $k$ (from $0$ to $n$) gives the result. – rogerl Nov 11 '15 at 16:18

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.