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.

This question already has an answer here:

I need to evaluate, for a certain worded question:

If n is even $$\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots\binom{n}{n}$$ If n is odd $$\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots\binom{n}{n-1}$$

I havent been able to reduce this using the binomial expansion.

share|improve this question
unrelated: why is the first binomial coefficient in the title bigger than the others? –  kuch nahi Jun 2 '11 at 15:35
related: math.stackexchange.com/questions/15591/… –  Grigory M Jun 2 '11 at 15:37
Just want to add that the original question was to find the number of binary sequences of length n that contain an even number of ones. Using a different argument the answer I got is $2^{n-1}$ –  kuch nahi Jun 2 '11 at 15:40
Hint: Do some computations for small values of $n$. You will see a pattern. When $n$ is odd, the pattern is most obviously proved by symmetry. When $n$ is even, look at Pascal's triangle. –  Aaron Jun 2 '11 at 15:41
add comment

marked as duplicate by Grigory M, Sasha, Daniel Fischer, hardmath, Dan Jan 16 at 22:19

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

6 Answers

up vote 20 down vote accepted

Binomial expansion allows one to find both $\binom n0+\binom n1+\binom n2+\dots=(1+1)^n$ and $(\binom n0-\binom n1+\binom n2+\dots)=(1-1)^n$. Combining these two yields desired result: $\binom n0+\binom n2+\binom n4+\dots=\frac12\bigl((1+1)^n+(1-1)^n\bigr)=2^{n-1}$.

share|improve this answer
I remember I've done this before. Thanks a ton! –  kuch nahi Jun 2 '11 at 15:45
The first version was helpful enough. Anyhow, thanks again. –  kuch nahi Jun 2 '11 at 15:54
add comment

The given sums count the number of even-cardinality subsets of an $n$-element set. I'll provide a simple argument that shows that the value of that sum is $2^{n-1}$.

Fix $x \in X$ (where $|X|=n$). The map $f \colon \mathcal{P}(X) \to \mathcal{P}(X)$ (where $\mathcal{P}(X)$ denotes the power set of $X$) defined by $$ f(Y) = \begin{cases} Y \cup \{x\} &\text{if } x \notin Y \\ Y - \{x\} &\text{if } x \in Y \end{cases} $$

is a bijection of $\mathcal{P}(X)$ that takes even-cardinality subsets to odd-cardinality subsets and vice-versa. Thus there are the same number of even-cardinality subsets as odd-cardinality subsets. Since there are $2^{n}$ total subsets, there must be $2^{n}/2 = 2^{n-1}$ even-cardinality subsets.

share|improve this answer
add comment

The sum of all binomial coefficients ${n \choose 0} + \cdots {n \choose n}$ is $2^n$. This is a well-known equation and the slick proof is to consider the binomial theorem for $(1+1)^n$.

Related is the binomial theorem applied to $(1-1)^n$ giving the sum

$${n \choose 0} - {n \choose 1} + {n \choose 2} - \cdots \pm {n \choose n} = 0.$$

The latter inequality is easy to see when you add up the $n$th row of Pascal's triangle with alternating signs and $n$ is odd. For example: $1-5+10-10+5-1 = 0$ is obvious from the symmetry of the entries.

To obtain the answer for every-other term in the first sum, you can add these two formulas together and the negative entries will cancel with the positive ones while the positive ones will double:

$$(1+1)^n + (1-1)^n = 2{n \choose 0} + 2{n \choose 2} + \cdots = 2^n + 0.$$

Now to finish, divide by two. To get the odd entries (the second part of your question), notice that $(1-1)^n = -(1-1)^n$ and use the technique above. Or you could just take the sum for all entries and subtract what we just obtained for the even entries.

share|improve this answer
add comment

Let $X$ be a binomial$(n,p)$ random variable with $p=1/2$. If $n$ is even, then the probability that $X$ is even is equal to $$ \sum\limits_{k = 0,2, \ldots ,n} {{n \choose k}\frac{1}{{2^n }}} . $$ On the other hand, this probability is obviously equal to $1/2$ (consider $X$ as the sum of $n$ independent random variables taking the values $0$ and $1$ with probability $1/2$ each). Hence, $$ \sum\limits_{k = 0,2, \ldots ,n} {{n \choose k}} = 2^n \frac{1}{2} = 2^{n - 1} . $$

share|improve this answer
+1: I'm always a fan of the probabilistic approach. :) –  Mike Spivey Jun 2 '11 at 16:37
@Mike - Thanks! –  Shai Covo Jun 2 '11 at 18:24
add comment

Here's a more general take. Sums of the form $\sum_k \binom{n}{2k} f(k)$ are sometimes called aerated binomial sums. My paper "Combinatorial Sums and Finite Differences" (Discrete Mathematics, 307 (24): 3130-3146, 2007) proves some general results about these aerated binomial sums. (See Section 4.) The case $f(k) = 1$ (as in the OP's question) falls out nicely.

Suppose you are interested, for some function $f(k)$, in the binomial sum

$$B(n) = \sum_{k=0}^n \binom{n}{2k} f(k).$$

Then, taking the finite difference $\Delta f(k) = f(k+1) - f(k)$, denote $A(n)$ by

$$A(n) = \sum_{k=0}^n \binom{n}{2k} \Delta f(k).$$

In the paper I prove that $B(n)$ and $A(n)$ are related via $$B(n) = 2^{n-1} f(0) + 2^n \sum_{k=2}^n \frac{A(k-2)}{2^k} + \frac{f(0)}{2}[n=0],$$ where $[n=0]$ evaluates to $1$ if $n=0$ and $0$ otherwise.

Since $f(k) = 1$ in the OP's question, $\Delta f(k) = 0$, and so $A(n) = 0$ for all $n$. Thus $$\sum_{k=0}^n \binom{n}{2k} = 2^{n-1} + \frac{1}{2}[n=0].$$

More generally, this approach can be used to prove that, for $m \geq 1$, $$\sum_k \binom{n}{2k} k^{\underline{m}} = n(n-m-1)^{\underline{m-1}} \, 2^{n-2m-1} [n \geq m+1],$$ and $$\sum_k \binom{n}{2k} k^m = n \sum_j \left\{ m \atop j\right\} \binom{n-j-1}{j-1} (j-1)! \, 2^{n-2j-1},$$ where $\left\{ m \atop j\right\}$ is a Stirling number of the second kind. (While the second equation swaps one sum for another, there are no more than $m$ terms in the right-hand side, and so it is useful when $m$ is small.)

The approach can also be extended to sums of the form $\sum_k \binom{n}{ak+b} f(k)$. (And the case $a = 2, b = 1$ is considered explicitly in the paper.) Using higher values of $a$ and $b$ would result in increasingly complicated expressions, though.

share|improve this answer
add comment

I think it might help to look at this in terms of the rows on pascal's triangle. The sum of a given row is 2^n. All rows are symmetric about the middle of the row. As this sounds like it could be HW, i'll leave it to you to figure out how each of those relate to the sum of the row.

share|improve this answer
I wish this were homework. As that would imply I am taking a course and have access to an instructor. –  kuch nahi Jun 2 '11 at 15:43
Ok, so they are both exactly half the of the row (they get every element once as opposed to twice). Since the sum of a row is 2^n, this gives 2^(n-1) as the answer. –  soandos Jun 2 '11 at 15:45
yup, got it. Thanks! +1 –  kuch nahi Jun 2 '11 at 15:54
add comment

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