I am currently reading Combinatorics 2nd ed. by R. Merris. I have a hard time getting what the author is trying to say on page 11, paragraph 1.2.2; theorem for Pascal's relation.
It says:
if 1 <= r <= n, then C(n + 1, r) = C(n, r - 1) + C(n, r).
Pascal’s relation implies, e.g., that C(6, 3) = C(5, 2) + C(5, 3) = 20.
Proof. Consider the (n + 1)-element set {x1, x2, xn, y}. Its r-element subsets can be partitioned into two families, those that contain y and those that do not. To count the subsets that contain y, simply observe that the remaining r - 1 elements can be chosen from {x1, x2, xn} in C(n, r - 1) ways. The r-element subsets that do not contain y are precisely the r-element subsets of {x1, x2, xn}, of which there are C(n, r).
In the book it counts the number of ways a subset of 2 numbers can be selected from a set of 5 numbers. There were 10 ways to do this and the author showed this by writing down all the combinations. But I can't figure out how C(6, 3) = C(5, 2) + C(5, 3) is equal to 20. How exactly does it work?
Also, why is 1 added to n in C(n + 1, r)? And why is there a y in the set?
Because the only way to choose an n-element subset from S is to choose all of its elements, C(n, n) = 1. Having n single elements, S has n single-element subsets, i.e., C(n, 1) = n. For essentially the same reason, C(n, n - 1) = n.
How come C(n, 1) is equal to n? Does the writer mean with the 1 the number of ways to choose?