0

I am struggling with this identity :

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

Thanks for your help

justadzr
  • 1,478
Jewgah
  • 29
  • 2
    This is also an algebraic identity, so you might try and prove it algebraically, if so a hint is the binomial theorem. If you want a combinatoric proof however, try and work out what each side is counting. – Joshua Tilley Jul 15 '20 at 10:10
  • Notice that the expression on the LHS counts the number of subsets containing fewer than half the elements of a set with an odd number of elements. – N. F. Taussig Jul 16 '20 at 10:05

2 Answers2

1

Let $$S=\sum_{k=0}^{n} {2n+1 \choose k}.$$ By binomial expansion $$(1+1)^{2n+1}=\sum_{j=0}^{n} {2n+1 \choose k}=1+{2n+1 \choose 1}+{2n+1 \choose 2}+{2n+1 \choose 3}+......+{2n+1 \choose n}+ {2n+1 \choose n+1}+{2n+1 \choose n+2}+.....+{2n+1 \choose 2n+1}=2^{2n+1}$$ Using the redlection propert of binomial cofficientafter $(n+1)$th term, we get $$(1+1)^{2n+1}=\sum_{j=0}^{n} {2n+1 \choose k}=1+{2n+1 \choose 1}+{2n+1 \choose 2}+{2n+1 \choose 3}+......+{2n+1 \choose n}+ {2n+1 \choose n-1}+{2n+1 \choose n-2}+.....+{2n+1 \choose 0}=2^{2n+1}$$ $$\implies 2S=2^{2n+1}\implies S=2^{2n}$$

Z Ahmed
  • 43,235
0

Consider the expansion of the binomial $$(x+1)^{2n+1}$$
And subsitute $x = 1$

Y.T.
  • 1,427
  • 9
  • 20