4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I like first solution :-) $\endgroup$ – xan Mar 31 '12 at 17:50
2
$\begingroup$

$\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\;.$$

$\endgroup$
  • $\begingroup$ This is beautiful what the combinatorial interpretation can do.. without counting :-) $\endgroup$ – xan Mar 31 '12 at 17:49
  • $\begingroup$ 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... $\endgroup$ – N. S. Mar 31 '12 at 18:06
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Mar 31 '12 at 18:09
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

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}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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