1
$\begingroup$

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

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

As for Pascal's Triangle (Pyramid?), I don't want to spoil it for you, but here's an illustration that indicates the relevant points:

Pascal's Triangle

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

$\endgroup$
2
  • $\begingroup$ Been trying to prove that it is also 2^(n-1) in a combinatorical way and could not reach a good answer. If you can help me with that I'll appreciate it! Thanks for the explanation above by the way! $\endgroup$
    – TheNotMe
    Apr 8, 2013 at 8:06
  • $\begingroup$ 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. $\endgroup$
    – Douglas S. Stones
    Apr 8, 2013 at 12:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .