Combinatorics -subsets containing at least $9$ elements

Question

How many subsets of the set $\{1,2..., 17\}$ contain at least $9$ elements Not in a form of sum.

I know the answer is $2^{16}$, but I don't know why.

Answer 1

HINT: There is a fact such as if $n$ is even, then: $$\binom{n+1}{1}+\binom{n+1}{3}+...+\binom{n+1}{n+1} = 2^{n}$$ which can be proven by induction for example. And we also have $$\binom{n}{k} = \binom{n}{n-k}$$

Now you can manipulate $$\binom{17}{9}+\binom{17}{10}+\binom{17}{11}+\binom{17}{12}+\binom{17}{13}+\binom{17}{14}+\binom{17}{15}+\binom{17}{16}+\binom{17}{17}$$ to get to the answer $2^{16}$.

Answer 2

Here an answer that I believe could build some additional intuition, even if the strategy could be shorter, as hinted in the comments and in other answers:

Total number of subsets of $\{ 1,2,...,17 \}$ is equal to $2^{17}.$ Here a trick to understand why. To construct a subset of the original set, assign to each element of the set the number $0$ or the number $1.$ The numer $0$ means that the element isn't in the set, and the number $1$ means that the element is in the set. So you have an equivalent problem now: The number of subsets is exactly the number of binary numbers with 17 digits. They are $2^{17}.$

Then you have to subtract from the previous result the number of subsets that don't have at least $9$ elements. So you have to subtract the number of binary numbers with seventeen digits but that have less than nine $1$s in them.

The number of binary numbers with seventeen digits and eight $1s$ are $\binom {17}{8}$ because this binomial means: "In how many ways can I choose eight things from seventeen?" that is equivalent to saying "In how many ways can I assign eight $1s$ to a number with seventeen digits?"

Number of binary numbers with seventeen digits and seven $1$s: $\binom {17}{7}$

Number of binary numbers with seventeen digits and six $1$s: $\binom {17}{6}$

$...$

Number of binary numbers with seventeen digits and zero $1$s: $\binom {17}{0}$

So the number of binary numbers with seventeen digits but that have less than nine $1$s in them is: $$\binom {17}{8}+\binom {17}{7}+\binom {17}{6}+\binom {17}{5}+\binom {17}{4}+\binom {17}{3}+\binom {17}{2}+\binom {17}{1}+\binom {17}{0}$$

So the final answer is $$2^{17} - \Biggl(\binom {17}{8}+\binom {17}{7}+\binom {17}{6}+\binom {17}{5}+\binom {17}{4}+\binom {17}{3}+\binom {17}{2}+\binom {17}{1}+\binom {17}{0}\Biggr) = 65536 = 2^{16} $$

EDIT:

I include the shorter answer too:

If you keep in mind the meaning of these binomials (in how many ways you can choose $n$ elements in a set of 17 elements - that also means how many subsets of $n$ elements are there in the set of 17 elements - $n$ being the number below in the binomial), than it's obvious that the answer is: $$\binom {17}{9} + \binom {17}{10} + \binom {17}{11} + \binom {17}{12} + \binom {17}{13} + \binom {17}{14} + \binom {17}{15} + \binom {17}{16} + \binom {17}{17} $$

You can also see this answer as the sum of all binary numbers with seventeen digits that contain at least nine $1$s.

Answer 3

Note that $$ 2^{17}=\sum_{k=0}^{17}\binom{17}{k}=2\sum_{k=9}^{17}\binom{17}{k}$$ since $$ \binom{17}{k}=\binom{17}{17-k}\quad (0\leq k\leq 17). $$ Hence $$ 2^{16}=\sum_{k=9}^{17}\binom{17}{k}. $$