Evaluate $\sum_{k=0}^n {{2n + 1}\choose {2k + 1}}$

Question

Evaluate $$ \sum_{k=0}^n {{2n + 1}\choose {2k + 1}} $$

I'm really stuck on this one, no idea how to progress. My best guess is to somehow get it into the form of $ n\choose k $ and then take that summation and work with that. Or maybe binomial theorem, but I'm very experienced with that. If you could give a breakdown on how to tackle these problems that'd be great!

Answer 1

Suppose you have $2n+1$ people to form a committee with.

There are $2^{2n+1}$ possible committees one could make (visit each person and ask if they want to be on the committee - yes or no).

Your summation counts only the committees having an odd number of people. There are just as many committees that have an even number of people (why?). Your summation therefore accounts for exactly half of all possible committees, so it must equal $2^{2n}$.

Answer 2

Hint:

By applying Binomial Theorem to $ (1-1)^{2n+1}=0 $, we have:

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

Move the negative terms to the right-hand side, we have:

$$ \binom{2n+1}{1}+\binom{2n+1}{3}+\cdots+\binom{2n+1}{2n+1}=\binom{2n+1}{0}+\binom{2n+1}{2}+\cdots+\binom{2n+1}{2n} .\tag{A}$$ And applying Binomial Theorem to $ (1+1)^{2n+1}=2^{2n+1} $, we have: $$ \binom{2n+1}{0}+\binom{2n+1}{1}+\binom{2n+1}{2}+\cdots+\binom{2n+1}{2n}+\binom{2n+1}{2n+1}=2^{2n+1} .\tag{B}$$

Further hint:

$$ 2\times (A)=(B) .$$

Answer 3

Hint:

$$2\sum_{k=0}^n\binom{2n+1}{2k+1}a^{2n-2k}b^{2k+1}=(a+b)^{2n+1}-(a-b)^{2n+1}=?$$

Set $a=b=1$

Answer 4

Solution $1$:

$$ \sum_{k=0}^{n}\binom{2n+1}{2k+1}\stackrel{\text{Pascal's}}=\sum_{k=0}^{n}\left(\binom{2n}{2k}+\binom{2n}{2k+1}\right)=\sum_{i=0}^{2n+1}\binom{2n}i=\sum_{i=0}^{2n}\binom{2n}i=2^{2n}. $$

Solution $2$:

The summation counts the number of odd-sized subsets of a set of size $2n+1$. Exactly half of these subsets are odd, because a set is odd if and only if its complement is even. That is, complentation is a bijection between even and odd subsets. Since there are $2^{2n+1}$ subsets total, half of which are odd, the number of odd subsets is $2^{2n}$.

Answer 5

Here's a part of the Pascal triangle:

Rows of this triangle are numbered from $0$, and the sum of $n$-th row is $\color{red}{2^n}$, because numbers in such row gives altogether count of all subsets of an $n$-element set, i. e. the number of elements in the power set of an $n$-element set.

Now note odd-numbered rows, e. g. the last one $\, (\text{the }5^\text{th})$. They have even number of elements, and the first is the same as the last, the second is the same as the last but one, etc. because of the know relation

$$\quad{n \choose k} = {n \choose {n-k}}$$

giving us

\begin{aligned} {5 \choose 0} &= {5 \choose 5} \\[1ex] {5 \choose 1} &= {5 \choose 4} \\[1ex] {5 \choose 2} &= {5 \choose 3} \\ \end{aligned}

Because in these equivalent pairs there is $1$-$1$ mapping between the even and odd "bottom" numbers $$0 \mapsto 5\\ 2 \mapsto 3\\ 4 \mapsto 1$$

the sum for the even, and and the sum for the odd ones must be the same, so it is a half of the total sum (for even and odd members):

$$\color{black}{{2^5\over 2} = 2^4 = 16}$$

for our particular number $5 = 2n+1$. For general solution we will use $(2n+1)$ instead of $5$, obtaining the result

$$\color{red}{{2^{2n+1}\over 2} = 2^{2n}}$$