Proving Series with Combination Hey guys I am trying to prove Bertrands postulate for a presentation. However, I need to prove some other lemmas to get to Bertrand's postulate.
My first thing is
$$\sum_{k=0}^{2n} {2n \choose k} = 4^n$$
So far I've tried by induction with base case n = 0
$$\sum_{k=0}^{0} {2n \choose k} = 1$$
and
$$4^0 = 1$$
Therefore for n = 0
$$\sum_{k=0}^{0} {2n \choose k} = 4^0$$
Now assume
$$\sum_{k=0}^{2x} {2x \choose k} = 4^x$$
We need to show
$$\sum_{k=0}^{2x+2} {2x+2 \choose k} = 4^{x+1}$$
Now
$$4^{x+1} = 4^x4 = 4\sum_{k=0}^{2x} {2x \choose k}$$
$$4\sum_{k=0}^{2x} {2x \choose k} = 4 [1 + \sum_{k=1}^{2x-1} {2x \choose k}]$$
From here I am lost. I am not sure if there is some combination rules that I am forgetting or something.
 A: Proof By Binomial Theorem
The binomial theorem can be used to prove this result.
$$(x+y)^n =\sum_{i=0}^n \binom{n}{i}x^iy^{n-i}$$
Putting $x,y$ as 1 and $n$ as $2n$ we get
$$2^{2n} =\sum_{i=0}^{2n} \binom{2n}{i}$$
$$4^{n} =\sum_{i=0}^{2n} \binom{2n}{i}$$
Proof by number of subsets in a set
Another way to do this is as suggested in the comments.
If a set has $n$ elements the number of ways to make subsets is:
The number of ways to make subsets with $0$ elements = $\binom{n}{0}$
The number of ways to make subsets with $1$ elements = $\binom{n}{1}$
The number of ways to make subsets with $2$ elements = $\binom{n}{2}$
.
.
.
.
.
The number of ways to make subsets with $n$ elements = $\binom{n}{n}$
Another way to  think about it is . Each element of the set can either be chosen or not therefore the total possibilities for unique subsets is 2^n.
Replacing n with 2n we get
$$4^{n} =\sum_{i=0}^{2n} \binom{2n}{i}$$
Proof by induction
Taking base case $0=n$
$$\binom{0}{0} = 1 = 4^0$$
Now assuming
$$\sum_{i=0}^{2n} \binom{2n}{i}= 4^n$$
We need to show that
$$\sum_{i=0}^{2n+2} \binom{2n+2}{i}= 4^{n+1}$$
We will use the fact
$$\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$$
First we will show that
$$\sum_{i=0}^{2n} \binom{2n}{i}+ \sum_{i=0}^{2n} \binom{2n}{i} =\sum_{i=0}^{2n+1} \binom{2n+1}{i}$$
Expanding and grouping terms together
$$ \binom{2n}{0} + \biggl(\binom{2n}{1}+\binom{2n}{0} \biggr) + \biggl(\binom{2n}{2}+\binom{2n}{1}\biggr) ........+\biggl(\binom{2n}{2n}+\binom{2n}{2n-1}\biggr) + \binom{2n}{2n}$$
Now using the fact given above
$$\binom{2n}{0} + \binom{2n+1}{1} + \binom{2n+1}{2}..........\binom{2n+1}{2n}+\binom{2n}{2n}$$
$$\binom{2n}{0} = 1 = \binom{2n+1}{0}$$
$$\binom{2n}{2n} = 1 = \binom{2n+1}{2n+1}$$
Replacing $\binom{2n}{0}$ and $\binom{2n}{2n}$ with $\binom{2n+1}{0}$ and $\binom{2n+1}{2n+1}$
We get:
$$\sum_{i=0}^{2n} \binom{2n}{i}+ \sum_{i=0}^{2n} \binom{2n}{i} =\sum_{i=0}^{2n+1} \binom{2n+1}{i}$$
Now we can use this result to show that
$$4\sum_{i=0}^{2n} \binom{2n}{i}=$$
$$2\sum_{i=0}^{2n+1} \binom{2n+1}{i}=$$
$$\sum_{i=0}^{2n+2} \binom{2n+2}{i}$$
Hence proved by induction
