# Combinatorics proof question

1. Mar 13, 2013

### hm8

1. The problem statement, all variables and given/known data

2. Relevant equations

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

3. 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.

2. Mar 13, 2013

### 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

3. Mar 13, 2013

### 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 ?

4. Mar 13, 2013

### Bacle2

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

5. Mar 13, 2013

### hm8

Still not quite getting it.

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

I think its the summation on the RHS thats 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

6. Mar 13, 2013

### tiny-tim

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 ?

7. Mar 13, 2013

### 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).

8. Mar 13, 2013

### 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.