Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|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






share|cite|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|cite|improve this answer
Thanks polkjh for nice solution – juantheron Jan 31 '13 at 5:35

Your Answer


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.