# Sum with binomial coefficients

I'm repeating material for test and I came across the example that I can not do. How to calculate this sum: $\displaystyle\sum_{k=0}^{n}{2n\choose 2k}$?

-

$$(1+1)^{2n}= \displaystyle\sum_{k=0}^{2n}{2n\choose k}$$ $$(1-1)^{2n}= \displaystyle\sum_{k=0}^{2n}(-1)^k{2n\choose k}$$

OR Second solution:

You can use the formula

$${2n\choose 2k}={2n-1\choose 2k}+{2n-1\choose 2k-1}$$ to prove that

$$\displaystyle\sum_{k=0}^{n}{2n\choose 2k}=\displaystyle\sum_{k=0}^{2n-1}{2n-1\choose k}$$

-
I like first solution :-) –  xan Mar 31 '12 at 17:50

$\binom{2n}{2k}$ is the number of subsets of $\{1,\dots,2n\}$ of size $2k$. When you sum these binomial coefficients over all $k$ from $0$ through $n$, you’re counting the number of subsets of $\{1,\dots,2n\}$ whose cardinalities are even. For $n>0$ exactly half of the subsets have even cardinalities, so the sum is $\frac12(2^{2n})=2^{2n-1}$.

Clearly $\{1\}$ has one even subset, $\varnothing$, and one odd subset, $\{1\}$. Suppose that $\{1,\dots,n\}$ has $2^{n-1}$ even and $2^{n-1}$ odd subsets. Now look at the $2^{n+1}$ subsets of $\{1,\dots,n+1\}$. Half of them are $2^n$ subsets of $\{1,\dots,n\}$, of which $2^{n-1}$ are even and $2^{n-1}$ are odd. The other $2^n$ subsets all contain $n+1$. The even ones are obtained by adding $n+1$ to an odd subset of $\{1,\dots,n\}$, so there are $2^{n-1}$ of them. The odd ones are obtained by adding $n+1$ to an even subset of $\{1,\dots,n\}$, so there are $2^{n-1}$ of them as well. Thus, $\{1,\dots,n+1\}$ has $2^{n-1}+2^{n-1}=2^n$ even subsets and the same number of odd subsets.

This does fail for $n=0$, since the empty set has only one subset, itself, and therefore has one even and no odd subsets. In that case $$\sum_{k=0}^n\binom{2n}{2k}=\binom00=1\;.$$

-
This is beautiful what the combinatorial interpretation can do.. without counting :-) –  xan Mar 31 '12 at 17:49
The counting is probably easier if you think instead of binary sequences of length $2n$ (these are exactly the subsets). Erasing the last digit of a binary string is a bijection between the binary strings of length 2n with even number of 1's and all the binary strings of length 2n-1... –  N. S. Mar 31 '12 at 18:06
@N.S.: Matter of taste. It’s just about six of one and half a dozen of the other, but for elementary presentations I prefer my version. –  Brian M. Scott Mar 31 '12 at 18:09

from binomial theorem we have

$$\sum_{i=0}^{2m}\binom{2m}{i}x^{i}=(1+x)^{2m}$$

for $x=1$ and $x=-1$ we get

$$\sum_{i=0}^{2m}\binom{2m}{i}=\sum_{k=0}^{2m}\binom{2m}{2k}+\sum_{k=1}^{2m}\binom{2m}{2k-1}=2^{2m}$$

$$\sum_{i=0}^{2m}\binom{2m}{i}(-1)^{i}=\sum_{k=0}^{2m}\binom{2m}{2k}-\sum_{k=1}^{2m}\binom{2m}{2k-1}=0$$ suming these equations we get $$2\sum_{k=0}^{2m}\binom{2m}{2k}=2^{2m}$$ finally

$$\sum_{k=0}^{2m}\binom{2m}{2k}=2^{2m-1}$$

-