The easiest way to see this is to consider bit strings.
\({n \choose k}\) is the number of bit strings of length
\(n\) containing
\(k\) 1βs. Of all of these strings, some start with a 1 and the rest start with a 0. First consider all the bit strings which start with a 1. After the 1, there must be
\(n-1\) more bits (to get the total length up to
\(n\)) and exactly
\(k-1\) of them must be 1βs (as we already have one, and we need
\(k\) total). How many strings are there like that? There are exactly
\({n-1 \choose k-1}\) such bit strings, so of all the length
\(n\) bit strings containing
\(k\) 1βs,
\({n-1 \choose k-1}\) of them start with a 1. Similarly, there are
\({n-1\choose k}\) which start with a 0 (we still need
\(n-1\) bits and now
\(k\) of them must be 1βs). Since there are
\({n-1 \choose k}\) bit strings containing
\(n-1\) bits with
\(k\) 1βs, that is the number of length
\(n\) bit strings with
\(k\) 1βs which start with a 0. Therefore
\({n \choose k} = {n-1\choose k-1} + {n-1 \choose k}\text{.}\)
Another way: consider the question, how many ways can you select
\(k\) pizza toppings from a menu containing
\(n\) choices? One way to do this is just
\({n \choose k}\text{.}\) Another way to answer the same question is to first decide whether or not you want anchovies. If you do want anchovies, you still need to pick
\(k-1\) toppings, now from just
\(n-1\) choices. That can be done in
\({n-1 \choose k-1}\) ways. If you do not want anchovies, then you still need to select
\(k\) toppings from
\(n-1\) choices (the anchovies are out). You can do that in
\({n-1 \choose k}\) ways. Since the choices with anchovies are disjoint from the choices without anchovies, the total choices are
\({n-1 \choose k-1}+{n-1 \choose k}\text{.}\) But wait. We answered the same question in two different ways, so the two answers must be the same. Thus
\({n \choose k} = {n-1\choose k-1} + {n-1 \choose k}\text{.}\)
You can also explain (prove) this identity by counting subsets, or even lattice paths.