Have to prove in a combinatorial and with pascal's pyramid

I have to prove that:

$$\sum_{k=0}^{(\lfloor \frac{n}{2} \rfloor)} { n \choose 2k} = 2^{n-1}$$

in two ways: A combinatorial way, and with the help of the Pascal Pyramid.

For the combinatorial way I thought about possibilities of choosing a set with an even number of elements, but the $$n \choose 0$$ ruins it all!

Any help will be appreciated

Your combinatorial argument is right, both sides of the equation count the number of subsets of $\{1,2,\ldots,n\}$ of even cardinality. Note that $\binom{n}{0}$ counts the empty subset. You should also probably add an argument as to why $2^{n-1}$ is the number of subsets of even cardinality.
(There is a slight difference between the $n$ even and $n$ odd cases.) Hopefully this provides sufficient inspiration. The relevant identity is $$\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}.$$
• Not wanting to spoil it, but $2^{n-1}=\frac{1}{2}2^n$. Thus, if we can "pair up" (=find a bijection between) the even-sizes subsets and the odd-sized subsets, we're done. Apr 8, 2013 at 12:24