ISI2015-MMA-5

Question

A set contains $2n+1$ elements. The number of subsets of the set which contain at most $n$ elements is

• A. $2^n$
• B. $2^{n+1}$
• C. $2^{n-1}$
• D. $2^{2n}$

Answer 1

Let the number of subsets of the set (of $2n+1$ elements) which contain at most $n$ elements be $\mathrm{M}$.

$$\therefore \mathrm{M}=\binom{2n+1}{0}+\binom{2n+1}{1}+\binom{2n+1}{2}+\cdots+\binom{2n+1}{n}$$

Now we know from binomial theorem that
$(1+x)^n=\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+\binom{n}{3}x^3+\binom{n}{4}x^4+\cdots+\binom{n}{n}x^n \tag{i}$

Besides $\binom{n}{r}=\binom{n}{n-r}$

From no$\mathrm{(i)}$, putting $x=1$ and $n \to (2n+1)$ yields

$\scriptsize \begin{align}(1+1)^{2n+1}&=\binom{2n+1}{0}+\binom{2n+1}{1}+\binom{2n+1}{2}+\cdots+\binom{2n+1}{n-1}+\binom{2n+1}{n}+\binom{2n+1}{n+1}+\binom{2n+1}{n+2}+\cdots+\binom{2n+1}{2n+1}\\ \Rightarrow 2^{2n+1}&=\binom{2n+1}{0}+\binom{2n+1}{1}+\binom{2n+1}{2}+\cdots+\binom{2n+1}{n-1}+\binom{2n+1}{n}+\binom{2n+1}{n}+\binom{2n+1}{n-1}+\cdots+\binom{2n+1}{0}\\ &=\mathrm{M}+\mathrm{M}=2\mathrm{M}\\ \therefore \mathrm{M} &=\frac{2^{2n+1}}{2}=2^{2n}\end{align}$

 

So the correct answer is D.

Comments

Perfect.

---

great one.. nicely done

Answer 2

This can be done by just taking a small value of n. Say value of $\text{n = 5}$

So the total size of set = 11, and number of subsets of containing atmost 5 elements can be

$=$ $11 \choose 0$ + $11 \choose 1$ + $11 \choose2 $ + $11 \choose 3$ + $11 \choose 4$ + $11 \choose 5$

$= \text{ 1 + 11 + 55 + 165 + 330 + 462}$

$ = \text{1024}$

$ =2^{10} \\= 2^{2*5}$

Hence answer must be option $D$