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

Thanks in advance!

Printable View

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

Thanks in advance! - June 10th 2010, 04: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 .

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

- June 12th 2010, 11:57 AMSpringFan25
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,

- June 12th 2010, 02:14 PMArchie Meade
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