# no. of subsets which have at least $r+1$ element is

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

-

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}$.

-
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}$.

-
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}$.

-
Thanks polkjh for nice solution – juantheron Jan 31 '13 at 5:35