Back to counting

In my first post on counting in two ways, I left as exercises to find combinatorial explanations for several identities.  In this post, I will explain the first two of them.  The first identity was
\[\sum_{k=0}^n {n\choose k} = 2^n.\]  If you're not familiar with the notation,

\[\sum_{k=0}^n {n\choose k} = {n\choose 0} +{n\choose 1} + \cdots + {n\choose n-1} + {n\choose n}.\]

So to use the example from a previous post, the left hand side is equal to the number of different ice cream cones you can have if there are $n$ different flavors and all the scoops are of distinct flavors (it counts the cones by the number of scoops since \(n\choose i\) counts the number of cones with $i$ scoops).  We want to show that the expression on the right hand side, $2^n$, counts the same thing.  
Now when we make a cone, for each flavor we have exactly two choices: either we include the flavor or we do not.  Since we have to make this choice for each of the $n$ flavors, the total number of possible cones is $2^n$.

The second identity I posted was
\[ \sum_{k=0}^{\lfloor\frac{n}{2}\rfloor} {n \choose 2k} = 2^{n-1}. \]   The notation $\lfloor\frac{n}{2}\rfloor$, pronounced 'floor of $\frac{n}{2}$', means that we take the largest integer less than or equal to $\frac{n}{2}$.  That is, if $n$ is even then $\lfloor\frac{n}{2}\rfloor=\frac{n}{2}$ and if $n$ is odd then $\lfloor\frac{n}{2}\rfloor=\frac{n-1}{2}$.  For simplicity, we will explain the identity when $n$ is even, but it will work just as well when $n$ is odd.  So when $n$ is even, the left had side is \[ \sum_{k=0}^{\frac{n}{2}} {n \choose 2k}={n\choose 0} + {n\choose 2} + \cdots + {n\choose n-2} + {n\choose n}.\]  We can see that this just sums the number of ice cream cones with an even number of scoops.  Since $2^{n-1} = \frac{2^n}{2}$, it suffices to show that the number of cones with an even number of scoops is equal to the number of cones with an odd number of scoops.  Let one of the flavors be vanilla.  Then the number of even scoop cones that contain vanilla is equal to the number of odd scoop cones that don't include vanilla (just remove vanilla from the cone!).  Similarly, the number of even scoop cones that do not include vanilla equals the number of odd scoop cones that do include vanilla (just add vanilla to the odd scoop cone).  This shows that the number of odd scoop cones equals the number of even scoop cones, and we are done.