Sum with binomial coefficients: $\sum_{k=0}^{n}{2n\choose 2k}$

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}$$

Using line integrals: taking $r>1$, \eqalign{2\pi i\sum_{k=0}^n\binom{2n}{2k} &= \sum_{k=0}^n\int_{|z|=r}\frac{(z + 1)^{2n}}{z^{2k+1}}\,dz = \sum_{k=0}^\infty\int_{|z|=r}\frac{(z + 1)^{2n}}{z^{2k+1}}\,dz = \int_{|z|=r}\frac{(z + 1)^{2n}}z\sum_{k=0}^{\infty}\frac1{z^{2k}}\,dz\cr &= \int_{|z|=r}\frac{(z + 1)^{2n}}z\,\frac1{1 - 1/z^2}\,dz = \int_{|z|=r}\frac{z(z + 1)^{2n-1}}{z-1}\,dz = 2\pi i\,2^{2n-1}. }


With $\ds{n \in \mathbb{N}_{\ \geq\ 0}}$:

\begin{align} \sum_{k = 0}^{n}{2n \choose 2k} & = \sum_{k = 0}^{2n}{2n \choose k}{1 + \pars{-1}^{k} \over 2} = {1 \over 2}\sum_{k = 0}^{2n}{2n \choose k}1^{k} + {1 \over 2}\sum_{k = 0}^{2n}{2n \choose k}\pars{-1}^{k} \\[5mm] & = {1 \over 2}\pars{1 + 1}^{2n} + {1 \over 2}\bracks{1 + \pars{-1}}^{2n} = \bbx{2^{2n - 1} + {1 \over 2}\,\delta_{n0}} \end{align}