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

Thanks in advance!

Printable View

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

Thanks in advance! - Jun 10th 2010, 03:26 PMPlato
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 $\displaystyle \binom{N}{K}=\frac{N!}{K!(N-K)!}$.

We can then read your question. - Jun 11th 2010, 08:41 AMmohammadfawaz
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.

- Jun 12th 2010, 10:57 AMSpringFan25
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)!$ - Jun 12th 2010, 01:14 PMArchie Meade
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}$