Combinatorics

cloudhorn

New member
Joined
Jun 26, 2014
Messages
5
I recently ran across a problem in my statistics course:

'Prove the identity "n choose k" = "(n-1) choose (k-1)" + "(n-1) choose k".'

How do I go about showing that that above is true?

If there is any ambiguity as to what the problem is about please let me know.
 
Hello, cloudhorn!

Prove the identity: .\(\displaystyle \displaystyle {n \choose k} \:=\: {n-1\choose k-1} + {n-1 \choose k}\)

On the right side we have:

. . \(\displaystyle \displaystyle{n-1\choose k-1} \;=\;\frac{(n-1)!}{(k-1)!(n-k)!} \)

. . \(\displaystyle \displaystyle{n-1\choose k} \;=\;\frac{(n-1)!}{k!(n-k-1)!}\)


\(\displaystyle \displaystyle {n-1\choose k-1} + {n-1\choose k} \;=\;\frac{(n-1)!}{(k-1)!(n-k)!} + \frac{(n-1)!}{k!(n-k-1)!} \)

. . \(\displaystyle \displaystyle =\; \frac{(n-1)!}{(k-1)!(n-k)!} \cdot \frac{k}{k} + \frac{(n-1)!}{k!(n-k-1)!} \cdot \frac{n-k}{n-k} \)

Try continuing from this point.
 
Last edited by a moderator:
Thank you both a bunch for your answers. I see now too that the first fraction was incorrect, but thanks nonetheless for the reply!
 
Top