Combinatorics with n case Show that if n is a positive integer, then 
$${2n\choose0} + {2n\choose2}+ \dots + {2n\choose2n} = 2^{2n-1}$$
I assume the proof is done by induction but how to I do the k+1 case?
 A: Suppose you want to take an even number of books out of $2n$ books with you on your holiday. The left hand side sums the number of possibilities over all possible amounts $2k$ to take with you. On the right hand side, for the first $2n-1$ books, you decide whether or not you take it with you. Then the last book is chosen only if you selected an odd number of books within the first $2n-1$ books. Now we have counted the same number of possibilities in two ways, resulting in
$$\sum_{k=0}^n\binom{2n}{2k}=2^{2n-1}$$
A: Apply Pascal's identity and then the binomial theorem. Alternatively, look at the expansion of $\frac{(1+x)^{2n} + (1-x)^{2n}}{2}$ and then plug in $x=1$.
A: The left side counts the number of subsets of a set with 2n elements that have an even number of elements, and there is a bijection between the subsets with an even number of elements and the subsets with an odd number of elements.
(See Exactly half of the elements of $\mathcal{P}(A)$ are odd-sized)
Since a set with 2n elements has $2^{2n}$ subsets, the left side must equal $2^{2n-1}$.
A: Hint: Use the Binomial theorem for:
$$(1+1)^{2n-1}$$
A: Consider that the sum of a row of Pascal's Triangle behaves this way:
$\dbinom{2n}{0}+\dbinom{2n}{1}+\dbinom{2n}{2}+\cdots+\dbinom{2n}{2n}=2^{2n}$
Also that:
$\dbinom{2n}{0}-\dbinom{2n}{1}+\dbinom{2n}{2}-\dbinom{2n}{3}+\cdots+(-1)^{2n}\dbinom{2n}{2n}=0$
Therefore:
$\dbinom{2n}{0}+\dbinom{2n}{2}+\cdots+\dbinom{2n}{2n}= \dbinom{2n}{1}+\dbinom{2n}{3}+\cdots+\dbinom{2n}{2n-1}$
And now you can conclude that: 
$2[\dbinom{2n}{0}+\dbinom{2n}{2}+\cdots+\dbinom{2n}{2n}]= 2^{2n}$
Finally, as stated:
$\dbinom{2n}{0}+\dbinom{2n}{2}+\cdots+\dbinom{2n}{2n}=2^{2n-1}$
