# Evaluating even binomial coefficients

Can someone give me a hint how to evaluate $$\binom{n}{0}+\binom{n}{2}+\cdots+\binom{n}{o(n)},$$ where $o(n)$ is $n$ if $n$ is even and $n-1$ otherwise ?

• – NoChance Mar 14 '12 at 21:33

Consider: $$\sum_{k=0}^n \binom{n}{k} x^k = (1+x)^n$$ Now you are computing: $$\sum_{m \geqslant 0, n \geqslant 2 m } \binom{n}{2m} = \sum_{k=0}^n \binom{n}{k} \frac{1+(-1)^k}{2} = \frac{(1+1)^n + (1-1)^n}{2} = \frac{2^n + \delta_{n,0}}{2}$$

We simply need to show the following two things: $$\sum_{i=0}^n \binom{n}{i} = 2^n$$ $$\sum_{i=0}^n (-1)^i\binom{n}{i} = 0$$

Both of these follow from the binomial formula. The result then follows routinely.

if n is odd then consider the below series:$$\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n} = 2^n$$ and we know that $$\binom{n}{k} = \binom{n}{n-k}$$ so $$\binom{n}{0} = \binom{n}{n} , \binom{n}{2} = \binom{n}{n-2} , ...$$ so for odd number the answer is $2^{n-1}$.

and for even number you can do the same thing like odd numbers.

If you calculate the first few examples, you'll see a very clear pattern-- if you haven't already done this, that's where you should start.

Now to prove this pattern and other patterns within the binomial coefficients, it's very helpful to use the fact that the binomial coefficient $\binom{n}{i}$ is just the coefficient of $x^iy^{n-i}$ in $(x+y)^n$.

You can prove that the sum $\binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \ldots + \binom{n}{n}=2^n$ just by setting $x=1$ and $y=1$ in the formula above to get $(1+1)^n$.

You can prove that the alternating sum $\binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \ldots +(-1)^n \binom{n}{n}=0$ just by setting $x=1$ and $y=-1$ in the formula above to get $(1-1)^n$.

Now what happens if you add these two sums together?

We have a group of $n$ people, where $n\ge 1$. The $n$-th person is George. The expression $$\binom{n}{0}+\binom{n}{2}+\cdots+\binom{n}{o(n)}$$ counts the number of ways to choose an even number of people from our group (including the possibility of choosing $0$ people).

Pick any set $S$ of people from the first $n-1$. If $S$ has an odd number of people, add George. If $S$ has an even number of people, leave George out.

We can thus see that there are just as many ways to choose an even number of people from $n$ people as there are ways to choose a set of people from $n-1$ people.

But this number is $2^{n-1}$, for in choosing people from the first $n-1$, for every person we have $2$ choices, yes or no.

Note that $n=0$ is an exception to the rule we have found, for $\binom{0}{0}=1$.

Let's first note that: $2^n = (1+1)^n = \sum_{i=0}^n \binom{n}{i}1^{n-i}1^i = \sum_{i=0}^n \binom{n}{i}$ and that $0 = (1 + (-1))^n = \sum_{i=0}^n\binom{n}{i} 1^{n-i}(-1)^i = \sum_{i=0}^n \binom{n}{i}(-1)^i$. We have then:\begin{align*} \sum_{i=0}^{n}\frac{1+(-1)^i}{2}\binom{n}{i} &= \frac{1}{2}\sum_{i=0}^{n}\binom{n}{i}(1+(-1)^i) \\ &= \frac{1}{2}\left( \sum_{i=0}^{n}\binom{n}{i} + \sum_{i=0}^{n}\binom{n}{i}(-1)^i \right) \\ &= \frac{1}{2}\left( 2^n + 0 \right) \\ &= 2^{n-1} \text{.} \end{align*}