# How many subsets are there?

I'm having trouble simplifying the expression for how many sets I can possibly have.

It's a very specific problem for which the specifics don't actually matter, but for $q$, some power of $2$ greater than $4$, I have a set of $q - 3$ elements. I am finding all subsets which contain at least two elements and at most half ($q / 2$, which would then also be a power of $2$) of the elements. I know that the total number of subsets which satisfy these conditions is (sorry my TeX may be awful),

$$\sum\limits_{i=2}^{\frac{q}{2}} \binom{q-3}{i}= \sum\limits_{i=0}^{\frac{q}{2}} \binom{q-3}{i}- (q - 3 + 1)$$

but I'm having a tough time finding a closed-form expression for this summation. I'm probably missing something, but it has stumped me this time.

-
Did you mean to write $$\binom{q-3}{i}$$ (\binom{q-3}{i}) instead of $$\begin{array}{c} q-3 \\ i\end{array}$$ (\begin{array}{c} q-3 \\ i\end{array})? – Zev Chonoles Jun 27 '12 at 0:53
Absolutely! I couldn't remember how to make that happen. – Kurtis Zimmerman Jun 27 '12 at 1:01

You're most of the way there; now just shave a couple of terms from the upper limit of your sum. Setting $r=q-3$ for clarity, and noting that $\lfloor r/2\rfloor = q/2-2$ (and that $r$ is odd since $q$ is a power of $2$),
$$\sum_{i=0}^{q/2}\binom{r}{i} = \binom{r}{q/2}+\binom{r}{q/2-1} + \sum_{i=0}^{\lfloor r/2\rfloor}\binom{r}{i}$$
And the last sum should be easy to compute, since by symmetry it's one half of $\displaystyle\sum_{i=0}^r\binom{r}{i}$...
@KurtisZimmerman Out of curiosity, what were you hoping for? That the answer wouldn't be exponential in $q$? Unfortunately, this is pretty easy to intuit even without an explicit formula; as $q$ gets large you can think of the binomials as the weights of a normal distribution, and you're using half of them minus a shrinking 'sliver' in the middle, so your answer was bound to be a positive fraction of the overall count (i.e., a positive fraction of $2^q$) regardless... – Steven Stadnicki Jun 27 '12 at 1:33