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