Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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})? –  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
add comment

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
Thanks for the help. The worst thing is when you've come upon the correct answer but it isn't what you had hoped. –  Kurtis Zimmerman Jun 27 '12 at 1:16
    
@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
    
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. ;) –  Kurtis Zimmerman Jun 27 '12 at 1:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.