# 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$?$

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

• 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. – Brian M. Scott Oct 29 '15 at 7:34
• Nearly correct, except for "- 1": don't. The empty set contains only even numbers. Really. Every number it contains is even. – BrianO Oct 29 '15 at 7:34
• Every number it contains also has bubble gum on its left sneaker on Tuesdays. – Matt Samuel Oct 29 '15 at 7:54
• 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". – fleablood Oct 29 '15 at 14:44
• 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. – jdods May 6 '16 at 11:45

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

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

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!!!