${2n \choose 1} + {2n \choose 3} + ... {2n \choose 2n-1}$

Question

$(1) \ \ \ \ {2n \choose 1} + {2n \choose 3} + ... {2n \choose 2n-1} = ?$

I know that $\sum_{k=0}^n {n \choose k} = 2^n$ and it is pretty easy to obtain, as it's an amout of all possible sets we can get from ${1,2,...,n}$. There is also a formula for $k = k + at$ $\forall_{a,t} \in R$, but it's pretty complicated, so I thought of figuring it by myself.

An assumption I made is that I can also express $(1)$ a bit differently:

$\sum_{k=0}^n {n \choose k} = \sum_{k=0}^n {n \choose 2k-1} + \sum_{k=0}^n {n \choose 2k} = A + B$. Let's take an example: $n = 4$. What I get is:

$A = {8 \choose 1} + {8 \choose 3} + {8 \choose 5} + {8 \choose 7}$

$B = {8 \choose 0} + {8 \choose 2} + {8 \choose 4} + {8 \choose 6} + {8 \choose 8}$

There comes a confusing part that I'm not sure at all, but let $A$ be an amount of all sets with an odd amount of elements, and same for $B$, but now we think of an even amount of sets with an even amount of elements. I thought:

$A + B + x_4 = 2^4 + 2^5 +x_4 = 2^8$

Then: $ x_4 = 2^4 \cdot 13$. Ok, kinda interesting due to the fact we get $2^4$. Having it done for a few more examples:

$x_2 = 2^2 \cdot 1$

$x_3 = 2^3 \cdot 5$

$x_4 = 2^4 \cdot 13$

$x_5 = 2^5 \cdot 29$

$x_6 = 2^6 \cdot 61$

$x_{2n} = 2^{2n} \cdot a_{2n}$

An intresting part is a series of these numbers $(5,13,29,61,...)$. It seems, that every following number $a_{2i} = a_{2i-1} + (n - 5) \cdot 8$. So if I knew whether the formula is true $\forall_{2n \in R}$ I could obtain, for example, $\sum_{k=1}^n {2n \choose 2k-1}$. But... is it true at all?

TL;DR What is an elegant way to obtain a sum ${100 \choose 1} + {100 \choose 3} + ... + {100 \choose 99}?$ Of course there is a formula I mentioned above:

But it's complicated and doesn't seem to be any useful during a test.

Note that there's a bijection between even and odd cardinality subsets. Expand $0=(1-1)^n$ by the binomial theorem, for example. — EuYu, Dec 04 '19 at 20:56
Ok, so $\sum_{k=0}^n {n \choose 2k-1} = \sum_{k=0}^n {n \choose 2k} = 2A$, then $ A = 2^{49}$. So I have basically used a cannon to kill a mosquito. Nice. — alladinsane, Dec 04 '19 at 21:05

score 2 · Accepted Answer · answered Dec 04 '19 at 22:29

We have the following binomial expansion: $$(1+1)^{2n}=\binom{2n}{0}+\binom{2n}{1}+\dots+\binom{2n}{2n}$$ and $$(1-1)^{2n}=\binom{2n}{0}-\binom{2n}{1}\pm\dots+\binom{2n}{2n}.$$ Summing both gives $$2^{2n}=2\binom{2n}{0}+2\binom{2n}{2}+\dots+2\binom{2n}{2n},$$ So dividing throughout by $2$ we get $$2^{2n-1}=\binom{2n}{0}+\binom{2n}{2}+\dots+\binom{2n}{2n}.$$ Of course, by subtracting this from the first equation (the binomial expansion of $(1+1)^{2n}$) we have $$2^{2n-1}=2^{2n}-2^{2n-1}=\binom{2n}{1}+\binom{2n}{3}+\dots+\binom{2n}{2n-1}.$$ The key trick here was to consider two different binomial expansions, one of which has alternating signs, and then exploit cancellation on every other term to isolate the terms we want to look at in the sum.

score 2 · Answer 2 · answered Dec 04 '19 at 23:09

Hint: The identity ${n\choose k}={n-1\choose k-1}+{n-1\choose k}$ tells us, for example, that

$${8\choose1}+{8\choose3}+{8\choose5}+{8\choose7}=\left({7\choose0}+{7\choose1}\right)+\left({7\choose2}+{7\choose3}\right)+\left({7\choose4}+{7\choose5}\right)+\left({7\choose6}+{7\choose7}\right)$$

${2n \choose 1} + {2n \choose 3} + ... {2n \choose 2n-1}$

2 Answers2