# n Choose k Formula

• June 10th 2010, 03:07 PM
meggnog
n Choose k Formula
Prove by induction on n that "n choose k" = (n!) / k!(n-k)!

• June 10th 2010, 03:26 PM
Plato
Quote:

Originally Posted by meggnog
Prove by induction on n that "n choose k" = (n!) / k!(n-k)!

Why in the world do you not learn to post in symbols? You can use LaTeX tags.
$$\binom{N}{K}=\frac{N!}{K!(N-K)!}$$ gives $\binom{N}{K}=\frac{N!}{K!(N-K)!}$.
• June 11th 2010, 08:41 AM
This formula was derived from the definition of $\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.
• June 12th 2010, 10:57 AM
SpringFan25
here is an outline that i think will work:

Step1: Show its true for $^nC_1$

Step2: Show that if it is true for $^nC_k$ then it must be true for $^{n}C_{k+1}$

Step 1: Show $^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 $^nC_k$ and $^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:
$^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 $^{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.
$^nC_{k+1} = ^nC_{k} * \frac{^{n-k}C_{1}}{k+1}$

$\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,
$(x+1)! = (x+1)x!$
$\frac{(x)!}{x} = (x-1)!$
• June 12th 2010, 01:14 PM
Quote:

Originally Posted by meggnog
Prove by induction on n that "n choose k" = (n!) / k!(n-k)!

If it was not clear (!!) that choosing k from n is $\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 $\binom{n}{k}=\frac{^nP_k}{k!}$

P(k)

Choose k from n is $\binom{n}{k}=\frac{n!}{(n-k)!k!}$

P(k+1)

Choose k+1 from n is $\binom{n}{k+1}=\frac{n!}{(n-[k+1])!(k+1)!}=\frac{n!}{(n-k-1)!(k+1)!}$

Proof

$\binom{n}{k+1}=\frac{n!}{(n-k-1)!(k+1)!}=\frac{(n-k)}{(n-k)}\ \frac{n!}{(n-k-1)!(k+1)k!}$

$=\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

$\frac{n-1}{2}\ \binom{n}{1}=\frac{n(n-1)}{2}$

$\binom{n}{2}=\frac{n!}{(n-2)!2!}=\frac{n(n-1)(n-2!}{(n-2)!2}=\frac{n(n-1)}{2}$