9
$\begingroup$

A set contains $\{1,2,3,4,5....n\}$ where $n$ is a even number. how many subsets that contain only even numbers are there for the set$?$

This is my solution, is this valid$?$

since number of single element subset that contain only a even number is: $n/2$ a element is either in or not in the subset, hence $2$ choices. Hence $2^{(n/2)}$ would give us all possible combinations of subset that contains only even number, including the empty set.

Hence my answer is given by $2^{(n/2)} - 1$. subtracting the $1$ because of the empty set $C(n,0)=1$.

$\endgroup$
  • 4
    $\begingroup$ It’s almost correct: you should not be subtracting $1$, since the empty set should be counted. A set contains only even numbers if it contains no odd numbers, and the empty set certainly contains no odd numbers. $\endgroup$ – Brian M. Scott Oct 29 '15 at 7:34
  • 2
    $\begingroup$ Nearly correct, except for "- 1": don't. The empty set contains only even numbers. Really. Every number it contains is even. $\endgroup$ – BrianO Oct 29 '15 at 7:34
  • 1
    $\begingroup$ Every number it contains also has bubble gum on its left sneaker on Tuesdays. $\endgroup$ – Matt Samuel Oct 29 '15 at 7:54
  • $\begingroup$ As no odd numbers will be in the set, the answer is the same as "How many subsets does {2,4, 6 .....n} have" which is the same as "How many subsets does a set with n/2 elements have". $\endgroup$ – fleablood Oct 29 '15 at 14:44
  • $\begingroup$ It seems likely that the question requires each set to contain at least one even number. Of course as stated, the question is a bit ambiguous. $\endgroup$ – jdods May 6 '16 at 11:45
0
$\begingroup$

A set consisting only of even numbers can be constructed in one of the following ways: $n/2\choose n/2$ ways to construct a set consisting of $n/2$ elements;

$n/2\choose (n/2) -1$ ways to construct a set consisting of $(n/2)-1$ elements;

$n/2\choose (n/2)-2$ ways to construct a set consisting of $(n/2)-2$ elements;

and so on and so forth until

$n/2\choose 1$ ways to construct a set consisting of $1$ element;

$n/2\choose 0$ ways to construct a set consisting of no elements;

Thus the total number of possible subsets is

$n/2\choose n/2$ + $n/2\choose (n/2)-1$ +...+$n/2\choose 1$+$n/2\choose 0$=$(2)^{n/2}$.

Remark: A set $S$ consisting of only even numbers means that if $x\in S$, then $x$ should be even. This is vacuously true if the set is empty and hence we should include $n/2\choose 0$.

$\endgroup$
  • 1
    $\begingroup$ While this is all correct, I think that proving the equality on the last line is harder than just using a straightforward method. $\endgroup$ – Kitegi Oct 29 '15 at 8:09
  • $\begingroup$ The combinatorical proof is basically what the OP says and is pretty straight forward at least to me. $\endgroup$ – cr001 Oct 29 '15 at 8:21
0
$\begingroup$

Lets prove this through recursion.

Let $a_n$ denotes the number of subsets of the set $S_n =\{1,2, \cdots , n\}$ containing even numbers only. Note that the null set is not a number(don't think it as 0) so we are not counting it.

Note that $a_{2n} = a_{2n+1}$ and $a_2 =1$

Now $$a_{2n+2} = a_{2n} + a_{2n} +1 = 2a_{2n} + 1 $$ Reasoning is based on the fact that the first $a_{2n}$ are the no. of even only subsets in $S_n$ and the second $a_{2n}$ denotes (those subsets only +the element "2n+2" ) is $S_{2n+2}$. The last 1 is for the subset {2n+2} only.

So, $$a_{2n+2} = 2a_{2n}+1 = 4a_{2n-2} +1 +2 = 2^n \cdot a_2 + \sum_{i=0}^{n-1} 2^i =2^n + 2^n -1 = 2^{n+1} - 1 $$

Hence, $$\boxed{a_{2n} = 2^n -1 }$$

Proved!!!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.