# prove, that following formula is correct

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

-
How about a combinatorical proof? Assume for a moment that $n$ is even, so you don't have to worry about rounding. What does the expression $n \choose k$ count? If so, what does the left hand count? And what does the right? Hint: The numbers of subsets of a set with $n$ elements is $2^n$. – levap Nov 5 '12 at 14:10
Hint: Also look at $(1+(-1))^n$. – Thomas Andrews Nov 5 '12 at 14:29
See that there is a correspondence between the number of subsets of a set with $n$ elements and the number of binary sequences with $n$ bits. What you want is just the number of sequences that ends with 0; that, in turn, is equal the ones that ends with 1. So there is $2^{n-1}$. – fmoura2005 Nov 5 '12 at 14:41
OK, i understand th ecombinatorical interpretation, but is it sufficient to prove that statement? i mean, is it enought to notice, that if we are counting subsets, there is twice as much as if we take every second. But is it manageable to show it with induction or something else? – fdhd Nov 5 '12 at 14:46
Ok sorry for stupid question, i checked Thomas Andrew hint, then it is obvious, thanks – fdhd Nov 5 '12 at 15:14

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

-