Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A Set has $2r+1$ elements. Then the no. of subsets which have at least $r+1$ element is

My Try::

selecting $r+1$ element from $2r+1$ which is $\displaystyle = \binom{2r+1}{r+1}$

selecting $r+2$ element from $2r+1$ which is $\displaystyle = \binom{2r+1}{r+2}$

..........................................................

..........................................................

selecting $2r+1$ element from $2r+1$ which is $\displaystyle = \binom{2r+1}{2r+1}$

So Total $ = \binom{2r+1}{r+1}+\binom{2r+1}{r+2}+..........+\binom{2r+1}{2r+1}$

and answer given is $ = 2^{2r}$

How can i Calculate it. Thanks

share|improve this question

3 Answers 3

up vote 1 down vote accepted

There are $2^{2r+1}$ total subsets of a set of $2r+1$ elements. Partition this set into 2 subsets. One subset must have at least $r+1$ elements while the other subset has $r$ elements or fewer. Therefore, for every subset of $r+1$ or more elements, there is a subset with less than $r+1$ elements. Therefore, the number of subsets with $r+1$ elements or more is $\frac12\times2^{2r+1}=2^{2r}$.

share|improve this answer
    
Thanks mike for nice solution –  juantheron Jan 31 '13 at 5:34
    
@juantheron I realized a little too late I had repeated polkjh's argument. I had considered taking deleting it before I decided it might be easier to comprehend. –  Mike Jan 31 '13 at 6:01

Substitute $x=1$ into $(1+x)^{2r+1}=\sum_{k=0}^{2r+1}\binom{2r+1}{k}x^k$ to get

$2^{2r+1}$

$=\sum_{k=0}^{2r+1}\binom{2r+1}{k}$

$=\sum_{k=0}^{r}\binom{2r+1}{k}+\sum_{k=r+1}^{2r+1}\binom{2r+1}{k}$

$=\sum_{k=0}^{r}\binom{2r+1}{2r+1-k}+\sum_{k=r+1}^{2r+1}\binom{2r+1}{k}$

$=2\sum_{k=r+1}^{2r+1}\binom{2r+1}{k}$.

share|improve this answer
    
thanks Jason Bourne –  juantheron Jan 31 '13 at 5:36

There is a one-one mapping between sets of size at least $r+1$ and sets of size at most $r$ (define the mapping as $X \rightarrow S-X$, S is the full set). So number of sets of size $\geq r+1$ is equal to number of sets with size $\leq r$. So half of all $2^{2r+1}$ sets have size $\geq r+1$.

You can also evaluate your expression and show it is same as $2^{2r}$. Note that $$ \binom{2r+1}{r+i} = \binom{2r}{r+i} + \binom{2r}{r+i-1} = \binom{2r}{r-i} + \binom{2r}{r+i-1} $$

Summing it over all $i=1,2,\ldots,r+1$ gives $\displaystyle \sum_{j=0}^{2r}{\binom{2r}{j}}$ which is equal to $2^{2r}$.

share|improve this answer
    
Thanks polkjh for nice solution –  juantheron Jan 31 '13 at 5:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.