Comparing Two Sums with Binomial Coefficients How do I use pascals identity:
$${2n\choose 2k}={2n-1\choose 2k}+{2n-1\choose 2k-1}$$ to prove that
$$\displaystyle\sum_{k=0}^{n}{2n\choose 2k}=\displaystyle\sum_{k=0}^{2n-1}{2n-1\choose k}$$
for every positive integer $n$ ?
 A: You have
$$
\sum_{k=0}^n\binom{2n}{2k}=\sum_{k=0}^n\left(\binom{2n-1}{2k}+\binom{2n-1}{2k-1}\right)
$$
Expand the right side. Here are first two and the last terms:
$$
\left(\binom{2n-1}{0}+\binom{2n-1}{-1}\right)+\left(\binom{2n-1}{2}+\binom{2n-1}{1}\right)+\cdots+\left(\binom{2n-1}{2n}+\binom{2n-1}{2n-1}\right)
$$
Do you see the pattern? Can you express this as a sum? There's only one slightly subtle point.
A: Other than Pascal's identity, we just notice that the sums on the right are the same because they cover the same binomial coefficients (red=even, green=odd, and blue=both).
$$
\begin{align}
\sum_{k=0}^n\binom{2n}{2k}
&=\sum_{k=0}^n\color{#C00000}{\binom{2n-1}{2k}}+\color{#00A000}{\binom{2n-1}{2k-1}}\\
&=\sum_{k=0}^{2n-1}\color{#0000FF}{\binom{2n-1}{k}}
\end{align}
$$
Note that $\binom{2n-1}{-1}=\binom{2n-1}{2n}=0$.
A: As an aside, I note that the identity 
$$\sum_{k=0}^{n}{2n\choose 2k}=\sum_{k=0}^{2n-1}{2n-1\choose k}\tag{1}$$
has an easy combinatorial proof that makes no use of Pascal’s identity. The lefthand side of $(1)$ obviously counts the number of even-sized subsets of $\{1,\dots,2n\}$. The righthand side counts all of the subsets of $\{1,\dots,2n-1\}$. The even-sized subsets of $\{1,\dots,2n\}$ that do not contain $2n$ are obviously in one-to-one correspondence with the even-sized subsets of $\{1,\dots,2n-1\}$, while the even-sized subsets of $\{1,\dots,2n\}$ that do contain $2n$ are in one-to-one correspondence with the odd-sized subsets of $\{1,\dots,2n-1\}$ by the map that throws away $2n$, so the even-sized subsets of $\{1,\dots,2n\}$ are in one-to-one correspondence with the subsets of $\{1,\dots,2n-1\}$, and $(1)$ follows immediately. (And of course both summations are equal to $2^{2n-1}$.)
Another way to say the same thing is to observe that for $n\ge 1$, half of the subsets of $\{1,\dots,n\}$ have even cardinality. (This is easily proved by induction, for instance.) $\{1,\dots,2n\}$ has $2^{2n}$ subsets; half of these, or $2^{2n-1}$, have even cardinality. But that’s the number of all subsets of $\{1,\dots,2n-1\}$.
It should be noted that $(1)$ holds only for $n>0$: if $n=0$, the lefthand side is $1$, and the righthand side is $0$.
A: HINT
Write out what you want to prove for $n = 1$ and $n = 2$. Use Pascal's identity. If you are stuck after this, update your question with your work and we'll go from there.
