0
$\begingroup$

Using mathematical induction, verify:

$${n \choose k} = \frac{n}{k} {n-1 \choose k-1}$$

For the base case, I need to have k=0? Or both n and k? When just k=0, there is a fraction with 0 as the denominator? The LHS is = 1, but I don't think this makes the RHS = 1...

Help?

$\endgroup$
4
  • $\begingroup$ Use en.wikipedia.org/wiki/Pascal's_rule with fix $k>0$ $\endgroup$ Feb 25, 2015 at 4:08
  • $\begingroup$ Induction is a fairly silly way to prove this identity; are you required to use it? $\endgroup$ Feb 25, 2015 at 4:10
  • $\begingroup$ ${n \choose k} = \frac{n}{k} {n-1 \choose k-1}$ iff $k{n \choose k} = n {n-1 \choose k-1}$ $\endgroup$
    – BigM
    Feb 25, 2015 at 4:29
  • $\begingroup$ Yes, it is required. $\endgroup$ Feb 25, 2015 at 13:07

1 Answer 1

2
$\begingroup$

$$\frac nk{n-1\choose k-1}=\frac nk\frac{(n-1)!}{((n-1)-(k-1))!(k-1)!}=\frac{n!}{(n-k)!k!}={n\choose k}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.