Can you explain the binomial identity \sumk=0n\binom{n}{k}2=\binom{2n}{n}?

[chaotixmonjuish]

\sum_k=0ⁿ\binom{n}{k}²=\binom{2n}{n}


Could someone give me a hint as to how to start this. I'm not sure how to really interpret it.



(n-k)\binom{n}{k}=n\binom{n-1}{k}
Right Side: Suppose you create a committe from \binom{n}{k}, then to pick a leader who isn't in the committee but in the pool of people, we have n-k ways.

Left Side: Suppose you have n ways to pick a leader for a group. After selecting the leader, you have n-1 people left to pick a committee of size k.

 

[tiny-tim]

Hi chaotixmonjuish !

(try using the X² and X₂ tags just above the Reply box )

∑_k=0^{n n}C_k² = ²ⁿC_n

Could someone give me a hint as to how to start this. I'm not sure how to really interpret it.

The RHS is the number of ways of choosing n people from 2n people.

Hint: Suppose the 2n people are n men and n women.

 

[chaotixmonjuish]

So would the right hand side be saying that suppose we had n men and n women, there are n ways to form a committee consisitng of both men and women.

 

[tiny-tim]

So would the right hand side be saying that suppose we had n men and n women, there are n ways to form a committee consisitng of both men and women.

uhhh?

the RHS is the same number, no matter how many men (or women) there are.

 

[chaotixmonjuish]

Uh oh, ha ha, now I'm confused...I feel like this binomial identiy has some really easy RHS.

 

[chaotixmonjuish]

Does it just count the number of ways to form a committee size of n from 2n people?

 

[tiny-tim]

Does it just count the number of ways to form a committee size of n from 2n people?

Yup!

Now … pretend the 2n people are n men and n women

 

[chaotixmonjuish]

Okay, so does it still mean n people regardless of gender?

 

[tiny-tim]

Okay, so does it still mean n people regardless of gender?

Yes … the RHS is still the same …

we wouldn't muck around with that! ​