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

Question

I'm trying to find the value of: $$\sum_{k=0}^{\left \lfloor \frac{p}{2} \right \rfloor} \binom{p}{k}$$ For even and odd $p$, the indication I was given suggests writing it as $$\frac{1}{2}\left (\sum_{k=0}^{\left \lfloor \frac{p}{2} \right \rfloor} \binom{p}{k} + \sum_{k=0}^{\left \lfloor \frac{p}{2} \right \rfloor} \binom{p}{p-k} \right )$$ But I nothing I did got me anywhere.

Answer 1

That's an excellent suggestion! Ceiling and floor functions are awkward, so my first step is always to remove them somehow:

Even $p$

For even $p$, we can define $p=2m$. Then the suggestion given to you become:

$$ \begin{aligned} \frac{1}{2}\left( \sum_{k=0}^{m}\binom{2m}{k} + \sum_{k=0}^{m}\binom{2m}{2m-k} \right) &= \frac{1}{2}\left( \sum_{k=0}^{m}\binom{2m}{k} + \sum_{k=m}^{2m}\binom{2m}{k} \right) \\\\ &= \frac{1}{2}\left( \binom{2m}{m}+\sum_{k=0}^{2m}\binom{2m}{k} \right) \\\\ &= \frac{1}{2}\left( \binom{p}{\frac{p}{2}}+2^{p} \right) \end{aligned} $$

Odd $p$

We define $p=2m+1$. Then the suggestion becomes:

$$ \begin{aligned} \frac{1}{2}\left( \sum_{k=0}^{m}\binom{2m+1}{k} + \sum_{k=0}^{m}\binom{2m+1}{2m+1-k} \right) &= \frac{1}{2}\left( \sum_{k=0}^{m}\binom{2m+1}{k} + \sum_{k=m+1}^{2m+1}\binom{2m+1}{k} \right) \\\\ &= \frac{1}{2}\left( \sum_{k=0}^{2m+1}\binom{2m+1}{k} \right) \\\\ &= \frac{1}{2}\cdot 2^{p} \end{aligned} $$

Key Points

• Always try to use the suggestion given to you by lecturer / book
• If an integer is odd or even, translate it to the equation using $p=2m$ or $p=2m+1$
• When there is a summation, try to change the index of summation
• Be familiar with binomial coefficients and their various well-known properties

Answer 2

You can write $$ \eqalign{ & 2^{\,p} = \sum\limits_{0\, \le \,k\, \le \,p} {\left( \matrix{ p \cr k \cr} \right)} = \cr & = \sum\limits_{0\, \le \,k\, \le \,\left\lfloor {{p \over 2}} \right\rfloor } {\left( \matrix{ p \cr k \cr} \right)} + \sum\limits_{\left\lfloor {{p \over 2}} \right\rfloor + 1\, \le \,k\, \le \,p} {\left( \matrix{ p \cr k \cr} \right)} = \cr & = \sum\limits_{0\, \le \,k\, \le \,\left\lfloor {{p \over 2}} \right\rfloor } {\left( \matrix{ p \cr k \cr} \right)} + \sum\limits_{\left\lfloor {{p \over 2}} \right\rfloor + 1\, \le \,k\, \le \,p} {\left( \matrix{ p \cr p - k \cr} \right)} = \cr & = \sum\limits_{0\, \le \,k\, \le \,\left\lfloor {{p \over 2}} \right\rfloor } {\left( \matrix{ p \cr k \cr} \right)} + \sum\limits_{0\, \le \,k\, \le \,p - \left\lfloor {{p \over 2}} \right\rfloor - 1} {\left( \matrix{ p \cr k \cr} \right)} = \cr & = \sum\limits_{0\, \le \,k\, \le \,\left\lfloor {{p \over 2}} \right\rfloor } {\left( \matrix{ p \cr k \cr} \right)} + \sum\limits_{0\, \le \,k\, \le \,\left\lceil {{p \over 2}} \right\rceil - 1} {\left( \matrix{ p \cr k \cr} \right)} = \cr & = \sum\limits_{0\, \le \,k\, \le \,\left\lceil {{p \over 2}} \right\rceil - 1} {\left( \matrix{ p \cr k \cr} \right)} + \sum\limits_{\left\lceil {{p \over 2}} \right\rceil \, \le \,k\, \le \,\left\lfloor {{p \over 2}} \right\rfloor } {\left( \matrix{ p \cr k \cr} \right)} + \sum\limits_{0\, \le \,k\, \le \,\left\lceil {{p \over 2}} \right\rceil - 1} {\left( \matrix{ p \cr k \cr} \right)} = \cr & = 2\sum\limits_{0\, \le \,k\, \le \,\left\lfloor {{p \over 2}} \right\rfloor } {\left( \matrix{ p \cr k \cr} \right)} + \left( {\left\lceil {{p \over 2}} \right\rceil - \left\lfloor {{p \over 2}} \right\rfloor - 1} \right)\left( \matrix{ p \cr \left\lfloor {{p \over 2}} \right\rfloor \cr} \right) = \cr & = 2\sum\limits_{0\, \le \,k\, \le \,\left\lfloor {{p \over 2}} \right\rfloor } {\left( \matrix{ p \cr k \cr} \right)} - \left( {1 - p\bmod 2} \right)\left( \matrix{ p \cr \left\lfloor {{p \over 2}} \right\rfloor \cr} \right) \cr} $$