# Compute ${11 \choose 1} + {11 \choose 3} + ... + {11 \choose 11}$?

I did this with brute force, and got 1024.

What is the faster method of solving this?

I don't know if this is the fastest method, but you can use the binomial theorem twice: $$2^{11}=(1+1)^{11}=\sum_{i=0}^{11}\binom{11}{i}$$ and $$0=(1-1)^{11}=\sum_{i=0}^{11}\binom{11}{i}(-1)^i.$$ Upon subtracting these two results and dividing by two, we obtain the result.

Since any time you choose an odd number of elements out of a set of eleven, you leave behind an even number of elements, $$\sum_{k\text{ odd}} \binom{11}{k} = \sum_{k\text{ even}} \binom{11}{k}$$

So the number of ways of choosing any subset of eleven elements is twice the number of ways of choosing an odd number of elements.

But to choose any subset, each element is either in our out of the chosen subset: Than gives $2^{11}$.

So the number of ways to choose an odd number of elements is $$\frac12\cdot 2^{11} = 2^{10} = 1024$$

P.S. This reasoning does not work when the main set has an even number of elements. But the property of the number of ways to choose an odd number of elements being half the total number of subsets still holds. Can you see why?

Since $\binom{11}{1}=\binom{11}{10},\binom{11}{3}=\binom{11}{8}$ and so on, $$\binom{11}{1}+\binom{11}{3}+\ldots+\binom{11}{11} = \binom{11}{10}+\binom{11}{8}+\ldots+\binom{11}{0}$$ so both the terms are half the sum $\binom{11}{0}+\binom{11}{1}+\binom{11}{2}+\ldots+\binom{11}{11}=2^{11}$, i.e. $2^{10}=\color{red}{1024}$.

• Why does it add up to a power of 2? Jan 11 '17 at 16:47
• @GerardL.: because there are $2^{11}$ subsets of $\{1,2,\ldots,10,11\}$, counted according to their cardinality or not. Alternatively, because: $$(1+x)^{11} = \sum_{k=0}^{11}\binom{11}{k}x^k$$ gives a power of $2$ at $x=1$. Jan 11 '17 at 17:38

Usually you break up ${n+1\choose k}, k\le n$ into ${n\choose k-1}+{n\choose k}$. This is one of the first tricks you learn from probably every baby probability textbook. For your problem:

$${11\choose 1}+{11\choose 3}+...+{11\choose 9}+{11\choose 11}=\left({10\choose 0}+{10\choose 1}\right)+\left({10\choose 2}+{10\choose 3}\right)+...+\left({10\choose 8}+{10\choose 9}\right)+{10\choose 10}=(1+1)^{10}$$

by recognizing ${11\choose 11}={10\choose 10}$.

You might recoginize ${m \choose n}$ as the co-efficient of the $x^n$ term in the binomial expansion of $(x+1)^m$

So the sum of all of the coefficients equals

$(1+1)^m$

In your example above only have the odd coefficients.

${11 \choose n} ={11 \choose 11-n}$

For every odd coefficient you have a symmetric even counterpart.

$\sum_\limits {i=0}^{5} {11\choose 2i+1} = \frac 12 \sum_\limits {i=0}^{11} {11\choose i} = 2^{10}$
