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

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.

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

Solution 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}\,.$$