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.

  • 2
    @Cameron. Where I come from, $\binom{2n-1}{-1}\text{ and }\binom{2n-1}{2n}$ are both defined to be zero. That's a fairly common extension.2012-10-26
  • 0
    Never seen that before, but that's good to know (and certainly intuitive). It might be worth noting explicitly in the answer, though, since the binomial coefficient is defined in many different ways depending on the source.2012-10-26
  • 0
    @Cameron. That's why I ended my answer as I did: that was my "subtle point."2012-10-26
  • 0
    thanks! i got it! but where can i find the definition of $${2n-1\choose -1}$$ and $${2n-1\choose 2n}$$? i never heard about it, and i would like to read more!2012-10-27
  • 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 $n2012-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
    how come they are equal to 0?2012-10-27
  • 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.