2

I am stuck with this problem: $\sum_\limits{k=0}^{n} {2n+1 \choose k}$.

I used Wolframalpha for the answer and is $4^n$. So i searched for a similar way to expressed it which is: $$4^n=(1+1)^{2n}=\sum_{k=0}^{2n}{2n \choose k}$$ Is there a way to prove that $\sum_\limits{k=0}^{2n}{2n \choose k}=\sum_\limits{k=0}^{n} {2n+1 \choose k}$?

Did
  • 279,727
Emma Wool
  • 457
  • 2
    Start with $2\times 4^n=(1+1)^{2n+1}=\sum_{k=0}^{2n+1}\binom{2n+1}{k}$ and use that $\binom{2n+1}{k}=\binom{2n+1}{2n+1-k}$ to show that $\sum_{k=0}^{2n+1}\binom{2n+1}{k}=2\sum_{0}^{n}\binom{2n+1}{n}$. – Hellen Sep 25 '17 at 13:30
  • For every positive $m$, $$\sum_k{m\choose 2k}+\sum_k{m\choose 2k+1}=\sum_i{m\choose i}=2^m$$ and $$\sum_k{m\choose 2k}-\sum_k{m\choose 2k+1}=\sum_i(-1)^i{m\choose i}=(1-1)^m=0$$ Solve this system from the unknowns $$x=\sum_k{m\choose 2k}\qquad y=\sum_k{m\choose 2k+1}$$ – Did Sep 25 '17 at 13:38

3 Answers3

3

Since $$\sum_{k = 0}^n \binom{2n + 1}{k} = \frac{1}{2}\left(\sum_{k = 0}^n \binom{2n + 1}{k} + \sum_{k = 0}^n \binom{2n + 1}{2n+1-k}\right) = \frac{1}{2}\sum_{k = 0}^{2n + 1} \binom{2n + 1}{k}$$

Then we have: $$\sum_{k = 0}^n \binom{2n + 1}{k} = \frac{1}{2}\sum_{k = 0}^{2n + 1} \binom{2n + 1}{k} = \frac{1}{2} \cdot 2^{2n + 1} = 2^{2n} = 4^n$$

Guy Fsone
  • 23,903
cip999
  • 1,996
  • Can you justify the first equality? – Guy Fsone Sep 25 '17 at 13:56
  • 2
    @GuyFsone $$\binom{2n + 1}{k} = \binom{2n + 1}{2n+1-k}$$ so $$\sum_{k = 0}^n \binom{2n + 1}{k} = \frac{1}{2}\left(\sum_{k = 0}^n \binom{2n + 1}{k} + \sum_{k = 0}^n \binom{2n + 1}{2n+1-k}\right) = \frac{1}{2}\sum_{k = 0}^{2n + 1} \binom{2n + 1}{k}$$ – mechanodroid Sep 25 '17 at 14:08
1

I post this as an answer rather than a comment...

Note that $ \binom{2n + 1}{k} =\binom{2n + 1}{2n+1-k} $

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

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

Therefore

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

You can conclude that

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

user577215664
  • 40,625
0

There is a very nice way to think about this problem:

The summation represents the number of subsets of all sizes $i: i\leq n$ from a set $A$ of size $2n+1$. Now, $$\begin{align*} | \mathcal{P}(A)| &= 2^{2n+1} \\ &=2\cdot 4^n \end{align*}$$ Is the number of every subset of $A$

But notice exactly half of the subsets of $A$ are of sizes less than or equal to $n$, so we have $4^n$ subsets, as required.

Jihoon Kang
  • 949