3
$\begingroup$

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 :)

$\endgroup$
6
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.