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

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!

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

• This is exactly what I needed. This analogy really helped me understand what this question was asking! Great response. I understand that it only accounts for the odd number of people because 2k+1 will always be odd, right? – Brownie Mar 28 at 1:21
• That's correct, and as $k$ ranges, you'll eventually visit every odd number. – Austin Mohr Mar 28 at 1:22

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

• Yea so my professor went over this problem in class, and he had these two different summations I'm still not sure of the "idea" of the problem. Could you explain please? – Brownie Mar 28 at 1:08
• @Brownie I have edited my post. The idea is to notice that the sum of odd terms and that of even terms are equal, and we can use this fact to substitute the terms in the binomial expansion of $(1+1)^{2n+1}=2^{2n+1}$. This is a very common trick, you had better remember it by heart. – Bach Mar 28 at 1:16
• Alright, I've gotten a lot of good answers. I can't say I still fully understand the solution, but this is a good start and I think I can figure it out. – Brownie Mar 28 at 1:17
• @Brownie Actually, there are two core facts: $(1-1)^n=0$ and $(1+1)^n=2^n$, then you use the Binomial Theorem. – Bach Mar 28 at 1:19
• Austin Mohr's, Mike Earnest's and your answers actually really helped clear this up. So if I'm understanding this correct and follow Mike Earnest's start and break it up into $\sum_{k=0}^{n}\left(\binom{2n}{2k}+\binom{2n}{2k+1}\right)$ then take those individual summations those together will be $2^{2n+1}$. I think? But since I'm only look at 1/2 it's only $2^{2n}? – Brownie Mar 28 at 1:29 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$$ • Could you break down your steps, I'm having trouble following, I'm at a very beginner level – Brownie Mar 28 at 1:09 • @Brownie, Can you make the two binomial expansion? – lab bhattacharjee Mar 28 at 1:10 • Sorry I don't think I've learned binomial expansion yet. You solution seems simple but I don't think I can follow – Brownie Mar 28 at 1:13 ### 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}$$. • Yes, This is the one I can follow best! My one question is about where you get$2n \choose i $I'm not sure how you made the jump to that. I see you changed the summation to go to$2^{n} +1$and then to &2n$ but I"m not sure what's happening – Brownie Mar 28 at 1:11
• @Brownie To see why that is true, just unpack both summations and see they are the same:$$\sum_{k=0}^{n} \left(\binom{2n}{2k}+\binom{2n}{2k+1}\right)=\left(\binom{2n}0+\binom{2n}1\right)+ \left(\binom{2n}2+\binom{2n}3\right) +\dots+ \left(\binom{2n}{2n}+\binom{2n}{2n+1}\right),$$ $$\sum_{i=0}^{2n+1}=\binom{2n}0+\binom{2n}1+\binom{2n}2+\binom{2n}3+\dots+\binom{2n}{2n}+\binom{2n}{2n+1}$$ – Mike Earnest Mar 28 at 1:19

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