Combinatorics -subsets containing at least $9$ elements 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.
 A: 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}$.
A: 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.
A: 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}.
$$
