Combinatorial proof for $\sum_{r=0} {n \choose {2r}} = \sum_{r=0} {n \choose {2r+1}} = 2^{n-1}$

Question

I have proved it algebraically like this.
Each of the terms in the odd sum can be broken into two terms using Pascal's rule.
That is, ${n \choose 1}={{n-1} \choose 0} + {{n-1} \choose 1}$
${n \choose 3}={{n-1} \choose 2} + {{n-1} \choose 3}$
${n \choose 5}={{n-1} \choose 4} + {{n-1} \choose 5}$ and so on. Thus I get $\sum_{r=0} {n \choose {2r+1}} = \sum_{r=0} {{n-1} \choose {r}}$.
Now, we know that $\sum_{r=0} {{n-1} \choose {r}} = 2^{n-1}$
Thus, the odd sum is $2^{n-1}$ and the even sum is $2^n - 2^{n-1} = 2^{n-1}$ and both are equal.
I am looking for some combinatorial proof of this formula.

Answer 1

These two numbers count the number of even-sized subsets and odd-sized subsets of $\{1,2,\ldots,n\}$. Taking the symmetric difference with $\{1\}$ interchanges even-sized and odd-sized subsets. There are the same number of each, so the two sums are equal. But the total number of subsets of an $n$-element set is $2^n$.

Answer 2

Since a combinatorial proof has been given, I am providing a linear-algebraic approach. Consider the linear functional $f:\mathbb{F}_2^n\to\mathbb{F}_2$ over the field $\mathbb{F}_2$ with two elements defined by $$f\left(x_1,x_2,\ldots,x_n\right)=x_1+x_2+\ldots+x_n$$ for all $x_1,x_2,\ldots,x_n\in\mathbb{F}_2$. We note that $f$ is surjective, so that the Rank-Nullity Theorem implies $$\dim_{\mathbb{F}_2}\big(\ker(f)\big)+1=\dim_{\mathbb{F}_2}\big(\ker(f)\big)+\dim_{\mathbb{F}_2}\left(\mathbb{F}_2\right)=\dim_{\mathbb{F}_2}\left(\mathbb{F}_2^n\right)=n\,.$$ Hence, $$\sum_{r=0}^{\lfloor n/2\rfloor}\,\binom{n}{2r}=\big|\ker(f)\big|=2^{\dim_{\mathbb{F}_2}\big(\ker(f)\big)}=2^{n-1}\,.$$

Answer 3

A bit of detail:

0) $(1+x)^n = \sum_{k=0}^{n}\binom{n}{k}x^k.$

1) $x=1$: $\sum_{k=0}^{n}\binom{n}{k} = 2^n$; I.e

there are $2^n$ subsets of a set of $n$ elements.

2) $x=-1$: $\sum_{k=0}^{n}\binom{n}{k}(-1)^k=0$.

Add 1) and 2):

3) $2 \sum_{k=0}^{n} \binom{n}{2k} = 2^n$; I.e.

there are $2^{n-1}$ 'even' subsets of a set of n elements.

Hence there are $2^{n-1}$ 'odd' subsets of a set of $n$ elements.

Finally :

$\sum_{k=0}^{n} \binom{n}{2k} = \sum_{k=0}^{n}\binom{n}{2k+1} = 2^{n-1}.$