How do I prove that $\sum_{k=0}^n \binom{2n}{k}=2^{2n-1} + \binom{2n-1}{n}$?

Question

I am trying to prove that, for all natural numbers $n\geq 1$, $$\displaystyle\sum_{k=0}^n\binom{2n}{k} = 2^{2n-1} + \binom{2n-1}{n}$$

---

I have checked it with computer up to $n=1000$. It is always true. But I do not know how to prove it.

I tried to use the identity which I know already.

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

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

If you add them up then it looks close to the answer on right side only.

$$\displaystyle\sum_{k=0}^n \left[\binom{n}{k}^2 + \binom{n}{k}\right] = 2^n + \binom{2n}{n}$$

But it is not the same. Off by $1$, should be $2n-1$ not $2n$.

Answer 1

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

Since ${n\choose k} = {n\choose n-k},$ we can say $\sum_\limits{k=0}^{n-1} {2n\choose k} = \sum_\limits{k=n+1}^{2n} {2n\choose k}$

$2\sum_\limits{k=0}^{n-1} {2n\choose k} = 2^{2n} - {2n\choose n}$

We must show that ${2n\choose n} = 2{2n-1\choose n}$

${2n\choose n} = \frac {(2n)!}{n!n!}$ by definition

Factoring $2n$ from the numerator and $n$ from the denominator.

$\frac {2n(2n-1)!}{n(n-1)!n!} = \frac {2(2n-1)!}{(n-1)!n!} = 2{2n-1\choose n}$

$2\sum_\limits{k=0}^{n-1} {2n\choose k} = 2^{2n} - 2{2n-1\choose n}\\ \sum_\limits{k=0}^{n-1} {2n\choose k} = 2^{2n-1} - {2n-1\choose n}\\ $

Answer 2

The calculation $2^{2n}=\sum_{k=0}^{2n}\binom{2n}{k}=2\sum_{k=0}^n\binom{2n}{k}-\binom{2n}{n}$ uses two facts, both with $m=2n$: $2^m=\sum_k\binom{m}{k}$ (partition subsets of a size-$m$ set by their size) and $\binom{m}{k}=\binom{m}{m-k}$ (pair subsets and their complements). So$$\sum_{k=0}^n\binom{2n}{k}=2^{2n-1}+\frac12\binom{2n}{n}=2^{2n-1}+\binom{2n-1}{n},$$since$$\frac12\binom{2n}{n}=\frac{(2n)!}{2\cdot n\cdot (n-1)!\cdot n!}=\frac{(2n-1)!}{(n-1)!n!}=\binom{2n-1}{n}.$$