How to prove combinatorial $\sum_{k=0}^{n/2} {n\choose2k} = \sum_{k=0}^{n/2 - 1} {n\choose2k+1} = 2^{n-1}$

Question

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?

Answer 1

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 $(*)$.

Answer 2

Let $S$ denote a set of size $n\ge 1$. Your first sum is the number of even-size subsets of $S$; the second sum counts the odd-size subsets instead. Fix some $a\in S$, then pair each $x\subseteq S\backslash\{a\}$ with $x\cup\{a\}$. Since each pair is one odd-sized set and one even-sized set, there are equally many of each, and that's $2^{n-1}$.

Answer 3

Hint: You can get the result by expanding these two expressions using the binomial theorem $$(1-1)^n=0\ \ \ \text{ and } \ \ \ (1+1)^n=2^n.$$