Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

3 Answers 3

up vote 2 down vote accepted

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

Add them together.

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

share|improve this answer
    
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\;.$$

share|improve this answer
    
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}$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.