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

Question

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

Answer 1

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

Answer 2

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

Answer 3

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