The Gateway to Computer Science Excellence
+1 vote
51 views

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

  1. $2^n$
  2. $2^{n+1}$
  3. $2^{n-1}$
  4. $2^{2n}$
in Set Theory & Algebra by Veteran (431k points)
retagged by | 51 views

2 Answers

+3 votes

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.

by Active (3.6k points)
edited by
+1
Perfect.
+1 vote
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$
by Active (2.4k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,385 answers
198,559 comments
105,383 users