How to prove combinatorial $\sum_{k=0}^{n/2} {n\choose2k} = \sum_{k=0}^{n/2 - 1} {n\choose2k+1} = 2^{n-1}$ I have problems solving the following formula for even positive integers $n$:
$$\sum_{k=0}^{n/2} {n\choose 2k} = \sum_{k=0}^{n/2 - 1} {n\choose 2k+1} = 2^{n-1}$$
I tried to prove it by induction but it didn't work. Is there any combinatorial proof?

For brevity we prove $$\sum_{k=0}^{n} \binom{2n}{2k} = \sum_{k=0}^{n-1} \binom{2n}{2k+1} = 2^{2n-1},\hspace{2cm}(*)$$ for $n\in\mathbb{N}$. It is sufficient to show that $\sum_{k=0}^{n} \binom{2n}{2k}=2^{2n-1}$ since we have
$$\sum_{k=0}^{n} \binom{2n}{2k} +\sum_{k=0}^{n-1} \binom{2n}{2k+1}=\sum_{k=0}^{2n} \binom{2n}{k} = 2^{2n}.\hspace{2cm}(**)$$ Let apply induction for $\sum_{k=0}^{n} \binom{2n}{2k}=2^{2n-1}$.
For $n=1$ equality is true. For $n=m$ assume equality is true, namely $\sum_{k=0}^{m} \binom{2m}{2k}=2^{2m-1}$(Here note that $\sum_{k=0}^{m-1} \binom{2m}{2k+1}=2^{2m-1}$ is also true by (**)). For $n=m+1$, 
\begin{eqnarray*}\sum_{k=0}^{m+1} \binom{2m+2}{2k}&=&\sum_{k=0}^{m+1}\left\{ \binom{2m}{2k-1}+\binom{2m}{2k-2}+\binom{2m}{2k}+\binom{2m}{2k-1}\right\}\\
&=&\sum_{k=0}^{m+1} \binom{2m}{2k}+ 2\sum_{k=0}^{m+1} \binom{2m}{2k-1}+\sum_{k=0}^{m+1} \binom{2m}{2k-2}\\
&=&\sum_{k=0}^{m} \binom{2m}{2k}+ 2\sum_{k=0}^{m+1} \binom{2m}{2k-1}+\sum_{k=0}^{m+1} \binom{2m}{2k-2}\\
&=&\sum_{k=0}^{m} \binom{2m}{2k}+2\sum_{k=0}^{m-1} \binom{2m}{2k+1}+\sum_{k=0}^{m} \binom{2m}{2k}\\
&=&4.2^{2m-1}=2^{2m+1}\end{eqnarray*} by use of $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$. Hence equality $\sum_{k=0}^{n} \binom{2n}{2k}=2^{2n-1}$ is valid for $n\in\mathbb{N}$ which implies $(*)$.
