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.

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