# Why, conceptually, is it that $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$? [duplicate]

Why, conceptually, is it that $$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}?$$ I know how to prove that this is true, but I don't understand conceptually why it makes sense.

• This question have been asked here many times. Neither of the answer to those questions was satisfactory to you? math.stackexchange.com/questions/86093/…, math.stackexchange.com/questions/392595/…, math.stackexchange.com/questions/20475/… and many other questions list there among linked questions. – Martin Sleziak Jan 4 '14 at 8:49
• Those posts were mostly discussing proofs for why this equality is true. After reading them, I still didn't feel that I understood the intuition behind it. I'm sorry if this question seems repetitive. – okarin Jan 4 '14 at 8:51
• But several of those posts have as one of the answers the same argument as in the answer you have accepted here... – Martin Sleziak Jan 4 '14 at 8:52
• The phrasing of the answer I accepted makes more sense to me than those. It is, however, possible that I might have missed an answer. – okarin Jan 4 '14 at 8:53
• At this point, I have gotten the answer that I was looking for, so whether or not you close does not concern me. – okarin Jan 4 '14 at 10:11

Sure. You're dividing into 2 cases. On the one hand you're saying I'm stuck choosing this element over here. So now I have r-1 more choices to make out of n-1 things. In the other case you're refusing that element. Now you've eliminated a choice, but still must pick r elements. These two cases are exhaustive and exclusive.

Because the number of ways that we can make a team of a certain size is equal to the number of ways that we can make a team of the same size without Fred, plus the number of ways we can make a team of size one smaller, plus Fred.

• dang. A deluge of answers just fell. – Andrew Marshall Jan 4 '14 at 6:40
• @Slade: Please, can you explain this similar identity also. Thank you. – Bumblebee Mar 7 '15 at 7:18
• @Nilan The number of ways we can pick a team of $r$ people, and then name one of them Bob, equals the number of ways we can name one person Bob, and then pick a team of $r-1$ other people. This generalizes to the case of more than one Bob. – Slade Mar 8 '15 at 3:23

The number of the combination that we choose $r$ people from $n$ people is the sum of the number of the combination that a person named $A$ is included and the number of the combination that $A$ is not included.

Another simple way to look at it is Pascal's triangle. This is simply a formulation of the rule that governs the triangle -- an entry is the sum of the two entries above it. The $i$-th entry in the $n$-th row is the sum of the $i-1$-th entry in the $n-1$-th row and the $i$-th entry in the $n-1$-th row. Hence, $$\binom{n-1}{i-1}+\binom{n-1}{i}=\binom{n}{i}$$

• This presumes that Pascal's triangle means something for binomial coefficients... – Ryan Reich Jan 4 '14 at 7:08

Consider picking $r$ objects out of a set of $n$ of them. Pick a particular object $O$. Either your set has $O$, or it doesn't. There are $\binom{n - 1}{r - 1}$ sets with $O$, and $\binom{n - 1}{r}$ sets without it. (Do you see why those are true?) So together, there are $\binom{n - 1}{r - 1} + \binom{n - 1}{r}$ sets of size $r$.

The number of ways of choosing $r$ items from $n$ distinct items is the same as

• choosing $r-1$ items from the first $n-1$ items (and add to the last item), plus
• choosing $r$ items from the first $n-1$ items (and not choosing the last item)