Prove by induction on n that "n choose k" = (n!) / k!(n-k)!
Thanks in advance!
This formula was derived from the definition of $\displaystyle \binom{N}{K}$. 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 $\displaystyle ^nC_1$
Step2: Show that if it is true for $\displaystyle ^nC_k$ then it must be true for $\displaystyle ^{n}C_{k+1}$
Step 1: Show $\displaystyle ^nC_1$ 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 $\displaystyle ^nC_k$ and $\displaystyle ^nC_{k+1}$ 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:
$\displaystyle ^nC_{k+1} = ^nC_{k} * \frac{^{n-k}C_{1}}{k+1}$
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 $\displaystyle ^{5}C_3$
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.
$\displaystyle ^nC_{k+1} = ^nC_{k} * \frac{^{n-k}C_{1}}{k+1}$
$\displaystyle \frac{n!}{(k+1)!(n-k-1)!} = \frac{n!}{k!(n-k)!} * \frac{(n-k)}{k+1}$
This is immediately obvious from the properties of the factorial function.
ie,
$\displaystyle (x+1)! = (x+1)x!$
$\displaystyle \frac{(x)!}{x} = (x-1)!$
If it was not clear (!!) that choosing k from n is $\displaystyle \binom{n}{k}$
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 $\displaystyle \binom{n}{k}=\frac{^nP_k}{k!}$
P(k)
Choose k from n is $\displaystyle \binom{n}{k}=\frac{n!}{(n-k)!k!}$
P(k+1)
Choose k+1 from n is $\displaystyle \binom{n}{k+1}=\frac{n!}{(n-[k+1])!(k+1)!}=\frac{n!}{(n-k-1)!(k+1)!}$
Proof
$\displaystyle \binom{n}{k+1}=\frac{n!}{(n-k-1)!(k+1)!}=\frac{(n-k)}{(n-k)}\ \frac{n!}{(n-k-1)!(k+1)k!}$
$\displaystyle =\frac{n-k}{k+1}\ \frac{n!}{(n-k)!k!}$
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
$\displaystyle \frac{n-1}{2}\ \binom{n}{1}=\frac{n(n-1)}{2}$
$\displaystyle \binom{n}{2}=\frac{n!}{(n-2)!2!}=\frac{n(n-1)(n-2!}{(n-2)!2}=\frac{n(n-1)}{2}$