Proving the Binomial Coefficient Formula with Mathematical Induction

[hm8]

Homework Statement

Homework Equations

{a \choose b} = \frac{a!}{(a-b)!b!}

The Attempt at a Solution

So I tried doing a mathematical induction proof (Show that it is true for some number, then show that if you assume it's true for 'k', it implies 'k+1')

I was able to get the initial step, to show that they are equal when k=1.

http://i.snag.gy/hss6O.jpg

But I'm stuck now. The math get impossibly messy and unworkable when trying to do the inductive step. If I could think of a actual situation (like choosing committees/chairmen) that could be counted either way, I could use a combinatorial proof, but I'm having trouble coming up with one.

 

[Bacle2]

Maybe you can see it this way ( sorry, I don't have time at the moment to look it thru carefully):

You are choosing 2k+1 members out of n by selecting 2k members overall--after

the 2k members have been selected, the extra one can only be the remaining one out

of the 2k+1 , and you are selecting your 2k elements from two pools of elements

( people; people, elements, potato-potatoe) first (i=k+1) you select from k in one

group and select the others from (n-k-1) others. Hope this can get you on the

right track.

select k out of

 

[tiny-tim]

hi hm8!

forget induction, you can do this directly!

the LHS is the number of ways of choosing 2k+1 objects from n

the RHS looks a lot like the number of ways of choosing 2k objects from n-1

hint: where is the missing object? and what is i ? ​

 

[Bacle2]

hi hm8!

forget induction, you can do this directly!

the LHS is the number of ways of choosing 2k+1 objects from n

the RHS looks a lot like the number of ways of choosing 2k objects from n-1

hint: where is the missing object? and what is i ? ​

Don't you mean what am i (sorry for the horrible joke)?

 

[hm8]

Still not quite getting it.

I understand that the LHS is the number of ways of choosing 2k+1 objects from n -- that's straightforward enough.

I think its the summation on the RHS that's confusing me. So for each step of the summation I'm choosing k things from two groups; k from a group that has one less than i objects in it, and then k more from a group that is i objects less than n. And I see that i goes from one more than k to n minus k in the summation...so the number of thing's were summing up is (n-k)-(k+1)= n-2k-1?

I guess I'm still really not seeing it

 

[tiny-tim]

… So for each step of the summation I'm choosing k things from two groups; k from a group that has one less than i objects in it, and then k more from a group that is i objects less than n. And I see that i goes from one more than k to n minus k in the summation...so the number of thing's were summing up is (n-k)-(k+1)= n-2k-1?

no

the number of things we're summing is the sum of the bottom lines, ie 2k

the number of things we're summing from is the sum of the top lines, ie n-1

so, as i asked before, where is the missing one? and what is (or am) i ?

 

[Bacle2]

Another way:

You want to count the number of ways of selecting 2k+1 ,say, people, out of 2n .

Then you do this by partitioning the 2n people into groups A,B with n-k≥ |A|,|B|≥k

and |A|+|B|=n-1 . Then choose k people from each, and throw in the one left out

(|A|+|B|=n-1).

 

[Bacle2]

You want to choose 2k+1 objects from 2n. You partition the n-1 people into two groups

adding to 2k ( i.e., you leave one out) . Then you select first :

i) k from k in group 1
ii) k from (n-k-1) in group 2 ( n-k-1+k =n-1)
iii) Throw in the one you left out

And then you increase group 1 by one person and decrease group 2 by 1 on each
iteration, each group choosing k.