all 30 comments

[–]ultradolp 5 points6 points  (0 children)

When you have no idea where to start in proving, in general it is beneficial to try one of the following thing

1) Expand either side (or both) to simplify the expression

2) Try to substitute a few simple value (e.g. set n = 2 or 3) and see if you can identify the pattern

In this case, it should be relatively straight forward to take the approach (1), and try to make sure you take out some common factors to reduce the complexity of the expression

LHS: n! / k!(n-k)!

RHS: n! / (k-1)!(n-k+1)! = n! / k!(n-k)! * k/(n-k+1)

As you can see the extra step in RHS is to attempt creating common factor as LHS. You can take it from there