Evaluate $ \binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots+\binom{n}{2k}+\cdots$ [duplicate]

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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

Answer 6

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.