2
$\begingroup$

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$ ?

  • 0
    Try writing out Pascal's identity for n = 1, 2, 3, 4 and writing out the equation that you're trying to prove for n = 4 (without simplifying the binomial coefficients). See if you can give a proof in that case. If you're able to do this, you'll see how to do the general case.2012-10-26

4 Answers 4

4

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.

  • 0
    @Tomer. Lots of people do this. For example, Knuth's *Concrete Mathematics*, Ch.5. In general, $\binom{n}{m}=0$ when m<0 and also when n. In other words, any integer pairs not in Pascal's triangle are zero.2012-10-27
3

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$.

  • 0
    Indeed! When $n=0$, $\binom{2n-1}{2n}=1$ instead of $0$.2012-10-27
2

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$.

  • 0
    @Tomer: there are three ways to look at this. The first is that $\binom{2n-1}{k}$ is the coefficient of $x^k$ in $(1+x)^{2n-1}$. The coefficients of $x^{2n}$ and $x^{-1}$ are $0$. The second is that, using $\binom{n}{k}=\frac{n!}{(n-k)!k!}$, $k\binom{2n-1}{k}=(2n-k)\binom{2n-1}{k-1}$; set $k=2n$ and $k=0$. The third is using Pascal's identity: $\binom{2n-1}{2n-1}+\binom{2n-1}{2n}=\binom{2n}{2n}$ and $\binom{2n-1}{-1}+\binom{2n-1}{0}=\binom{2n}{0}$.2012-10-27
1

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.