1

How is $C(n,r) = C(n-1, r-1) + C(n-1,r)?$ I am watching P & C video from here

I have read that suppose we have n distinct inputs. We have two possibilities:

1) Can select

2) Not select

If I select one from n then I am left with $C(n-1, r-1)$ and if I don't select I am left with $C(n-1, r)$.

I don't understand this $C(n-1, r)$ part. If I don't select how did the total elements turn $n-1$ shouldn't they still remain $n$. Any mathematical proof to prove the equality or understand it better?

Winther
  • 24,478
abhimanyuaryan
  • 125

1 Answers1

3

Here are two proofs of Pascal's Identity.

Algebraic Method: \begin{align*} \binom{n - 1}{r - 1} + \binom{n - 1}{r} & = \frac{(n - 1)!}{(r - 1)![n - 1 - (r - 1)]!} + \frac{(n - 1)!}{r!(n - 1 - r)!}\\ & = \frac{(n - 1)!}{(r - 1)!(n - r)!} + \frac{(n - 1)!}{r!(n - r - 1)!}\\ & = \frac{(n - 1)!r}{(r - 1)!(n - r)!r} + \frac{(n - 1)!(n - r)}{r!(n - r - 1)!(n - r)}\\ & = \frac{(n - 1)!r}{r!(n - r)!} + \frac{(n - 1)!(n - r)}{r!(n - r)!}\\ & = \frac{(n - 1)!(r + n - r)}{r!(n - r)!}\\ & = \frac{(n - 1)!n}{r!(n - r)!}\\ & = \frac{n!}{r!(n - r)!}\\ & = \binom{n}{r} \end{align*}

Combinatorial Method: A subset of $r$ elements can be selected from a set of $n$ elements in $$\binom{n}{r}$$ ways. Suppose we wish to select $r$ elements from the set $\{x_1, x_2, \ldots, x_{n - 1}, x_n\}$. There are two possibilities. The subset either contains the element $x_n$, or it does not. If $x_n$ is one of the $r$ elements in the subset, we must select $x_n$ and $r - 1$ elements from the subset $\{x_1, x_2, \ldots, x_{n - 1}\}$, which can be done in $$\binom{1}{1}\binom{n - 1}{r - 1} = \binom{n - 1}{r - 1}$$ ways. If $x_n$ is not one of the $r$ elements in the subset, we must select $r$ elements from the subset $\{x_1, x_2, \ldots, x_{n - 1}\}$, which can be done in $$\binom{n - 1}{r}$$ ways. Hence, the number of ways of selecting $r$ elements from a set with $n$ elements is $$\binom{n}{r} = \binom{n - 1}{r - 1} + \binom{n - 1}{r}$$

N. F. Taussig
  • 76,571