Proving Pascal's Rule : $\binom n k =\binom{n−1}{ k−1}+\binom{n−1} k $

Question

I have taken the R.H.S and used the combination formula $$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$ then I don't know other steps to solve it.

Answer 1

If you take ${n\choose k}=\frac{n!}{k!(n-k)!}$ for granted, then

$${n-1\choose k-1}+{n-1\choose k}=\frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!}{k!(n-k-1)!}\\ =\frac{k(n-1)!}{k!(n-k)!}+\frac{(n-k)(n-1)!}{k!(n-k)!}\\ =\frac{(n-1)!}{k!(n-k)!}\left(k+n-k\right)=\frac{n!}{k!(n-k)!}={n\choose k}$$

Answer 2

Here is a procedure to choose $k$ things from $n$ things. It is well known that there are $\binom{n}{k}$ ways to do this.

Pick the first item. It is either used or not.

• if it is used, we must pick $k-1$ things from $n-1$ remaining things, which we can do in $\binom{n-1}{k-1}$ ways
• it is is not used, we must pick all $k$ things from $n-1$ remaining things, which we can do in $\binom{n-1}{k}$ ways

Can you complete the argument?

Answer 3

Hint

If you want to do this purely algebraically (and your question suggests that you do), you can look at the right hand side (using the definitional formula you displayed). You get a pair of fractions. One has denominator $$ (k-1)! ( (n-1) - (k-1) )! $$ which is the same as $$ (k-1)! ( n - k )! $$ The other has denominator $$ k! (n-k)! $$ So to put them over a common denominator, multiply the first one by $\frac{k}{k}$. THen you can combine numerators, factor out a (very large) common factor, and simplify, and you'll end up with the left-hand side.