As in the statement, I got problems with:$\binom{n}{0} +\binom{n}{2}+\binom{n}{4}+\cdots+\binom{n}{2[\frac{n}{2}]}=2^{n-1}$ I started with Newton conjecture, trying to work with $(1+1)^n=\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}$ but actually it does not guide me anywhere. i would appreciate any hints, since it looks a bit strange to me
prove, that following formula is correct
-
0Ok sorry for stupid question, i checked Thomas Andrew hint, then it is obvious, thanks – 2012-11-05
2 Answers
The root of the solution lies in the fact, $\binom n {2[\frac{n}{2}]}$ is the last term of $(1+1)^n+(1-1)^n$ as proved below:
for $n=2m, [\frac n2]=[\frac{2m}2]=m, \binom n {2[\frac{n}{2}]}=\binom{2m}{2m}$
for $n=2m+1, [\frac n2]=[\frac{2m+1}2]=m ,\binom n {2[\frac{n}{2}]}=\binom{2m+1}{2m}$
Now,
$2^{2m}=(1+1)^{2m}=\binom{2m}{0} +\binom{2m}1 +\binom{2m}2+\cdots+\binom{2m}{2m-1}+\binom{2m}{2m}$
$0=(1-1)^{2m}=\binom{2m}{0} -\binom{2m}1 +\binom{2m}2+\cdots-\binom{2m}{2m-1}+\binom{2m}{2m}$
Adding we get, $2^{2m}=2\left(\binom{2m}{0}+\binom{2m}2+\cdots+\binom{2m}{2m-2}+\binom{2m}{2m} \right)$
$2^{2m-1}=\binom{2m}{0}+\binom{2m}2+\cdots+\binom{2m}{2m-2}+\binom{2m}{2m}--->(1)$
Replacing $2m$ with $n$ and $\binom{2m}{2m}$ with $\binom n {2[\frac{n}{2}]}$ we get, $2^{n-1}=\binom n 0+\binom n2+\cdots+\binom n{n-2}+\binom n {2[\frac{n}{2}]}$
Similarly,
$2^{2m+1}=(1+1)^{2m+1}=\binom{2m+1}{0} +\binom{2m+1}1 +\binom{2m+1}2+\cdots+\binom{2m+1}{2m}+\binom{2m+1}{2m+1}$
$0=(1-1)^{2m+1}=\binom{2m+1}{0} -\binom{2m+1}1 +\binom{2m+1}2-\cdots+\binom{2m+1}{2m}-\binom{2m+1}{2m+1}$
Adding we get, $2^{2m+1}=2\left(\binom{2m+1}{0}+\binom{2m+1}2+\cdots+\binom{2m+1}{2m-2}+\binom{2m+1}{2m} \right)$
$2^{2m}=\binom{2m+1}{0}+\binom{2m+1}2+\cdots+\binom{2m+1}{2m-2}+\binom{2m+1}{2m}--->(2)$
Replacing $2m+1$ with $n$ and $\binom{2m+1}{2m}$ with $\binom n {2[\frac{n}{2}]}$ we get, $2^{n-1}=\binom n 0+\binom n2+\cdots+\binom n{n-2}+\binom n {2[\frac{n}{2}]}$
Let $X$ be a set with $n$ elements (for example $X = \{1,\ldots, n\}$) and $x \in X$. Consider the map \begin{align*} f_x\colon \mathscr P(X) &\to \mathscr P(X)\\ A&\mapsto \begin{cases} A \cup\{x\} & x \not\in A\\ A \setminus \{x\} & x \in A\end{cases} \end{align*} on the power set of $X$. Note that $f_x$ is a bijection (being its own inverse) and changes the parity of each subset of $X$. Hence $f_x$ restricts to a bijection between then "even" subsets and the "odd" subsets (meaning the parity of the cardinality of the sets). So there are exactly as many even sets as there are odd ones, that is there are $2^{n-1}$ even subsets. As there are $\binom nk$ subsets of size $k$, we have \[ 2^{n-1} = \sum_{k=0}^{\lfloor \frac n2\rfloor} \binom n{2k}. \]