n Choose k Formula

**meggnog** · June 10th 2010, 03:07 PM

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

Thanks in advance!

**Plato** · June 10th 2010, 03:26 PM

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.
[tex]\binom{N}{K}=\frac{N!}{K!(N-K)!}[/tex] gives $\binom{N}{K}=\frac{N!}{K!(N-K)!}$ .
We can then read your question.

**mohammadfawaz** · 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.

**SpringFan25** · June 12th 2010, 10:57 AM

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)!$

**Archie Meade** · June 12th 2010, 01:14 PM

Originally Posted by meggnog

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

Thanks in advance!

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}$

Thread: n Choose k Formula

LinkBack

Thread Tools

Display

n Choose k Formula

Similar Math Help Forum Discussions

n choose k

how to choose

not sure which on to choose

how do you choose which half angle formula (tan) to use?

Choose from set

Search Tags