Prove by induction on n that "n choose k" = (n!) / k!(n-k)!
Thanks in advance!
This formula was derived from the definition of . How are you planning to prove it by induction? you can go to an example and prove that choosing a set of K elements from a large set of N elements can occur in that number of ways but I'm not sure about induction.
here is an outline that i think will work:
Step1: Show its true for
Step2: Show that if it is true for then it must be true for
Step 1: Show is correct
This is trivial so I'll leave it to you. (substitute k=1 in your formula, and see that you get n as the answer)
Step 2
Find the relationship between and and show your proposition has this property.
Think: How can i choose (k+1) from n?
i can choose (k) from n, then choose 1 more from the remainder. There will be duplicates in this method that must be adjusted for. Each combination is duplicated exactly k+1 times. (Corresponding to the (k+1) positions that the "1 from the remainder" could take in the combination).
So:
The final adjustment of (k+1) on the right hand side is to remove duplicate combinations. Every combination appears (k+1) times, corresponding to the (k+1) positions that the "1 more" selected can take. I've done it with n=4 as an example below:
Aside: Duplicate combinations
Lets find
If Yes = Selected and No = Not slected, there are the usual 10 combinations
YYYNN
YYNYN
....
Now, lets get all the combinations by choosing 2 from 5 (Y), and 1 more from the remainder (y). two items are not selected (N).
if i use this algorithm, i can choose the "first 3" exactly 3 ways
YYyNN
YyYNN
yYYNN
all these are the same combination (first 3 selected).
You can repeat this for all other ways of getting 5C3 if you like, and every combination will appear 3 times in the same way. This generalises to (k+1) which gives the adjustment in the formula below
/Aside
Now, wee need to show that this relationship holds for your formula.
This is immediately obvious from the properties of the factorial function.
ie,
If it was not clear (!!) that choosing k from n is
and there was a suspicion that the formula was valid (!!!)
then "Proof by Induction" can verify it,
though surely it's simpler to realise that
P(k)
Choose k from n is
P(k+1)
Choose k+1 from n is
Proof
Is this the number of ways to choose k+1 from n?
To have an extra element in the selection, there are n-k to choose from.
Any of those n-k elements can join the original k elements to form a selection of k+1.
However, this new selection, having k+1 terms now, has k+1 ways to arrive at it, since any of k+1 new elements can have formed it from an original selection of k elements.
Hence, the result obtained is correct.
Finally test for k=1