i cant find an expression for:

$\sum_{k=0}^{\lfloor \frac{p}{2}\rfloor}$ ${p}\choose{k}$

The hint given by the exercise is to do it by seperating the cases where p is odd and even.

What I did so far: When $p$ is even, $\lfloor p/2 \rfloor = p/2$, so all we need is find an expression $\sum_{k=0}^{ \frac{p}{2}}$ ${p}\choose{k}$, which I was not able to do.

When $p$ is odd, there is $q$ so that $p=2q+1$ and $p/2= q +1/2$ which means $\lfloor p/2 \rfloor = q$, and I really dont know what to do with this.

The previous question was to show that functions that are of the form $ax+b$ are both convex and concave.

I thought that I should try to put some values in to look for a pattern and here is what I have : for $p$ even :

$p=2, \sum_{k=0}^{1}$ ${2}\choose{k}$$=1+2=3$

$p=4, \sum_{k=0}^{2}$ ${4}\choose{k}$$=1+6+4=11$

$p=6, \sum_{k=0}^{3}$ ${6}\choose{k}$$=1+6+15+20=42$

no apparent pattern.

when p is odd,

$p=1, \sum_{k=0}^{0}$ ${1}\choose{k}$$=1$

$p=3, \sum_{k=0}^{1}$ ${3}\choose{k}$$=1+3=4$

$p=5, \sum_{k=0}^{2}$ ${5}\choose{k}$$=1+5+10=16$

$p=7, \sum_{k=0}^{4}$ ${7}\choose{k}$$=1+7+21+35+35=99$

No apparent pattern here

Thank you for your help

  • 1
    $\begingroup$ Your calculation for $p=7$ is wrong. $\endgroup$ – Robert Israel Jan 13 at 21:14

We have ${p \choose k} = {p \choose p-k}$, so $$ \sum_{k=0}^{\lfloor p/2 \rfloor} {p \choose k} = \sum_{k = p - \lfloor p/2 \rfloor}^p {p \choose k}$$ Thus if $p$ is odd, $\{0, \ldots, \lfloor p/2 \rfloor \}$ and $\{p - \lfloor p/2 \rfloor, \ldots, p\}$ are disjoint and their union is $\{0, \ldots, p\}$, so using the binomial theorem your sum is $2^{p-1}$. If $p$ is even, $p/2$ is in both sets, so your sum is $2^{p-1} + {p \choose p/2}/2$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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