# What's $\sum_{k=0}^n\binom{n}{2k}$?

How do you calculate $\displaystyle \sum_{k=0}^n\binom{n}{2k}$? And doesn't the sum terminate when 2k exceeds n, so the upper bound should be less than n?

EDIT: I don't understand the negging. Have I violated a rule of conduct or something?

• "Have I violated a rule of conduct?" Well, technically... you're supposed to show effort every time you ask a question, so some people will just automatically downvote unless you include your own attempt in the question. – Jack M Aug 10 '14 at 1:08
• Good to know. Thanks. – Caddyshack Aug 10 '14 at 1:21

First of all, $\dbinom{n}{m} = 0$ if $m > n$. Hence, $\displaystyle\sum_{k = 0}^{n}\dbinom{n}{2k} = \sum_{k = 0}^{\lfloor n/2 \rfloor}\dbinom{n}{2k} = \sum_{\substack{0 \le m \le n \\ m \ \text{is even}}}\dbinom{n}{m}$.

To help you calculate the sum, note that by the binomial theorem:

$2^n = (1+1)^n = \displaystyle\sum_{m = 0}^{n}\dbinom{n}{m}1^m = \sum_{\substack{0 \le m \le n \\ m \ \text{is even}}}\dbinom{n}{m} + \sum_{\substack{0 \le m \le n \\ m \ \text{is odd}}}\dbinom{n}{m}$

$0 = (1-1)^n = \displaystyle\sum_{m = 0}^{n}\dbinom{n}{m}(-1)^m = \sum_{\substack{0 \le m \le n \\ m \ \text{is even}}}\dbinom{n}{m} - \sum_{\substack{0 \le m \le n \\ m \ \text{is odd}}}\dbinom{n}{m}$.

Do you see how to finish?

• Yes, I do, I think. We add the two lines. But there's a bit I don't get. I don't understand how you got the floor bit. I knew the upper bound would be less than n but didn't know how to see what it was. How do you do/see this? Thanks. – Caddyshack Aug 10 '14 at 1:14
• We only need to sum over $k$ such that $0 \le 2k \le n$, i.e. $0 \le k \le n/2$. So, the upper bound is the largest integer less than or equal to $n/2$, i.e. $\lfloor n/2 \rfloor$. – JimmyK4542 Aug 10 '14 at 1:18
• Brilliant, thank you! – Caddyshack Aug 10 '14 at 1:19

Recall that each binomial coefficient is the sum of the two above it in Pascal's triangle.

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ $\ds{\sum_{k = 0}^{n}{n \choose 2k}:\ {\large ?}}$

$$\mbox{Note that}\quad\sum_{k = 0}^{n}{n \choose 2k} =\sum_{k = 0}^{\color{#c00000}{\large\infty}}{n \choose 2k}.$$

$$\mbox{We'll use the identity}\quad {m \choose s}=\oint_{0\ <\ \verts{z}\ =\ a} {\pars{1 + z}^{m} \over z^{s + 1}}\,{\dd z \over 2\pi\ic}\,,\quad s \in {\mathbb N}$$

Then, \begin{align} &\color{#66f}{\large\sum_{k = 0}^{n}{n \choose 2k}} =\sum_{k = 0}^{\infty}\oint_{\verts{z}\ =\ a\ >\ 1} {\pars{1 + z}^{n} \over z^{2k + 1}}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ a\ >\ 1}{\pars{1 + z}^{n} \over z} \sum_{k = 0}^{\infty}\pars{1 \over z^{2}}^{k}\,{\dd z \over 2\pi\ic} \\[3mm]&=\oint_{\verts{z}\ =\ a\ >\ 1}{\pars{1 + z}^{n} \over z} {1 \over 1 - 1/z^{2}}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ a\ >\ 1}{\pars{1 + z}^{n}\,z \over \pars{z - 1}\pars{z + 1}} \,{\dd z \over 2\pi\ic} \\[3mm]&={\pars{1 + 1}^{n}\times 1 \over 1 + 1}=\color{#66f}{\large 2^{n - 1}} \end{align}

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

BECAUSE:

$$\sum_{k=1}^n \binom{n}{2k}=\binom{n}{2}+\binom{n}{4}+\binom{n}{3}+ \dots$$

$$(x+y)^n=\sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}$$

$$x=1,y=1: \sum_{k=0}^n \binom{n}{k}=\binom{n}{1}+\binom{n}{2}+\binom{n}{3}+ \dots=2^n$$

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

• How did you calculate it? – Caddyshack Aug 10 '14 at 0:59
• look at my edited answer. – user159870 Aug 10 '14 at 1:03
• Could you explain the second equality in the last line, please? – Caddyshack Aug 10 '14 at 1:05
• At the second sum ,k takes all numbers from 1 to n,at the first only the multiples of two,so the second is 2 x the first. – user159870 Aug 10 '14 at 1:10
• Where do you get $\sum_{k=1}^n{n\choose 2k} = {n\choose 2}+{n\choose 4}+{n\choose 3}+\ldots$ from?? And yeah, the second equality in the last line makes literally no sense - there's no innate reason to believe that the half of the coefficients you remove will be equal to the half that you don't remove. The result is correct (I believe), but the reasoning to get there is entirely specious. – Steven Stadnicki Aug 10 '14 at 1:26