How to prove that $\sum_{k=0}^n \binom{2n+1}{2k+1} = 4^{n}$

Question

My question is how to prove that $\sum_{k=0}^n \binom{2n+1}{2k+1} = 4^{n}$ . I'm not good at operating on the sign of sum, so please, try to explain me that as clearly as possible. Thanks :)

Answer 1

Hint: Your left hand side of the equation is equal to all the ways to choose a subset of odd size from a set of size $2n + 1$.

Answer 2

Use the binomial theorem, then you have $$4^n=(1+1)^{2n}=\sum_{k=0}^{2n}\binom{2n}k=\sum_{k=0}^n\binom{2n+1}{2k+1}$$ by grouping succesive coefficients together, i.e. $\binom{2n}{2k}+\binom{2n}{2k+1}=\binom{2n+1}{2k+1}$, except for the last one where $\binom{2n}{2n}=1=\binom{2n+1}{2n+1}$.

If you don't want to discuss the last coefficient separatedly, just note that if you set extra coefficients to $0$ (as is usually done), the formulas for coefficients still hold and you can write $$\sum_{k=0}^{2n}\binom{2n}k=\sum_{k=0}^\infty\binom{2n}k=\sum_{k=0}^\infty\binom{2n+1}{2k+1}=\sum_{k=0}^n\binom{2n+1}{2k+1}$$

Answer 3

Add $$\sum_{k=0}^n {2n+1 \choose 2k}$$ to get $2^{2n+1}=2\cdot 4^n$ and $$\sum_{k=0}^n {2n+1 \choose 2k}=\sum_{k=0}^n{2n+1 \choose 2n+1-2k}=\sum_{k=0}^n{2n+1 \choose 2k+1}.$$