1
$\begingroup$

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.

  • 1
    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}`)?2012-06-27
  • 0
    Absolutely! I couldn't remember how to make that happen.2012-06-27

1 Answers 1

2

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

  • 0
    Thanks for the help. The worst thing is when you've come upon the correct answer but it isn't what you had hoped.2012-06-27
  • 0
    @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...2012-06-27
  • 0
    I know you're right, but I didn't want to believe that it would be so large for the sake of my problem size. It was one of those situations where I thought I had stumbled on something halfway-clever, but it has proven to be futile. ;)2012-06-27