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.
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Recall that $\sum_{k=0}^p\binom{p}{k}=(1+1)^k$. $\endgroup$ – Robert Z Nov 17 '18 at 15:57
-
$\begingroup$ Look at Pascal's triangle. The p-th row consists of the values $p \choose k$. Maybe you can notice a pattern when you sum 1/2 the values in a row. $\endgroup$ – Joel Pereira Nov 17 '18 at 16:02
Add a comment
|
$\begingroup$
$\endgroup$
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} $$
