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

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.

• Try looking at this question. Sep 2, 2019 at 18:31

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?

• I think i could not. can you provide me the clear explanation with solution of problem. Please! Sep 2, 2019 at 18:13
• @GoneLastvirus This is not a "we do your homework for you site" -- the general policy here is that the OP is expected to display some sort of effort in working on the problem, and we are here to guide, but not to do people's work for them. With that in context, how many ways are there to complete the outlined strategy? Sep 2, 2019 at 18:19
• @ gt6989b sorry sir, i am not doing my homework i am just preparing for my exam so i need some steps only that makes me clear about the problem. Sep 2, 2019 at 18:29

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}$$

• will you please explain me second steps. you have multiply first one by k/k or ? Sep 2, 2019 at 18:36
• Thanks @Jean-Claude Arbaut i get that step. Sep 2, 2019 at 18:43

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.

• Thanks you so much. Sep 2, 2019 at 18:32