Even vs. Odd in a combinatoric proof

**RespeckKnuckles** · January 1st 2011, 11:36 PM

I was given a problem to simplify the following:
$\sum_{k \geq 0} \binom{n}{2k}$
where:
$\binom{n}{j} = 0$ whenever j > n.
It's easy to see that the problem is equivalent to:
$\sum_{k = 0}^n \binom{n}{2k}$

Now I can see that for odd values of n, this expands to:
$\binom{n}{0} + \binom{n}{2} + ... + \binom{n}{n-1}$
and since:
$\binom{n}{n-1} = \binom{n}{1}, \binom{n}{n-3} = \binom{n}{3}, ...$
we can use the last n/2 terms to "fill in the gaps", simplifying it to be:
$\frac{\sum_{k=0}^n \binom{n}{k}}{2} = \frac{2^n}{2} = 2^n-1$

That's easy. But I don't know why the proof still works for even numbers of n. You no longer have the same correspondence (n choose 0 no longer has the equivalent n choose n-1 as a term):
$\binom{n}{0} + \binom{n}{2} + ... + \binom{n}{n-2} + \binom{n}{n}$
So it can't "fill in the gaps" in the same way.

Can anyone figure this out? I've been at this for hours and the explanations I'm being given by the texts are just crap.

**Drexel28** · January 2nd 2011, 12:23 AM

Originally Posted by RespeckKnuckles

I was given a problem to simplify the following:
$\sum_{k \geq 0} \binom{n}{2k}$
where:
$\binom{n}{j} = 0$ whenever j > n.
It's easy to see that the problem is equivalent to:
$\sum_{k = 0}^n \binom{n}{2k}$

Now I can see that for odd values of n, this expands to:
$\binom{n}{0} + \binom{n}{2} + ... + \binom{n}{n-1}$
and since:
$\binom{n}{n-1} = \binom{n}{1}, \binom{n}{n-3} = \binom{n}{3}, ...$
we can use the last n/2 terms to "fill in the gaps", simplifying it to be:
$\frac{\sum_{k=0}^n \binom{n}{k}}{2} = \frac{2^n}{2} = 2^n-1$

That's easy. But I don't know why the proof still works for even numbers of n. You no longer have the same correspondence (n choose 0 no longer has the equivalent n choose n-1 as a term):
$\binom{n}{0} + \binom{n}{2} + ... + \binom{n}{n-2} + \binom{n}{n}$
So it can't "fill in the gaps" in the same way.

Can anyone figure this out? I've been at this for hours and the explanations I'm being given by the texts are just crap.

Here is a combinatorial proof. Clearly $\displaystyle \sum_{k=0}^{n}{n\choose {2k}}$ counts the number of subsets of $[n]$ with
an even number

of elements. Call the set of subsets with an odd number elements of $[n]$ $O_n$ and the set of subsets with an

even number elements $E_n$ . We claim that $\#\left(E_n\right)=\#\left(O_n\right)$ for every $n\in\mathbb{N}$ . The result is clearly true

for $n=1$ . Suppose it's true for $[n]$ and note that $[n+1]$ can be partitioned into the subsets of $[n+1]$

which contain $n+1$ and those that don't, call this partition $\{B_1,B_2\}$ (with $B_1$ being the collection

of subsets not containing $n+1$ ) it's evident that $O_{n+1}$ is equal to the number of subsets with an odd number

of elements of $B_1$ plus the number of subsets of $B_2$ with an odd number of elements and similarly for $E_{n+1}$ .

But, it's clear that the number of subsets of $B_1$ with an odd number of elements is $O_{n}$ and the number of

subsets of $B_1$ with an even number of elements is $E_n$ . But, a little thought shows that the number of

subsets with an even number of elements in $B_2$ is $O_n$ and the number of subsets with an odd number of

elements is $E_n$ . Thus, $O_{n+1}=O_n+E_n$ and $E_{n+1}=O_n+E_n$ from where the conclusion follows by

induction. Thus,

$\displaystyle \begin{aligned}\sum_{k=0}^{n}{n\choose 2k} &=\frac{1}{2}\left(\#(E_n)+\#(E_n)\right)\\ &= \frac{1}{2}\left(\#(E_n)+\#(O_n)\right)\\ &= \frac{1}{2}2^n\\ &= 2^{n-1}\end{aligned}$

Remark: Incidentally we've proven that $\#2([n])=\#([n+1])$ and since $\#(2^{\varnothing})=1$ we may conclude that

$\#([n])=2^n$

**BAdhi** · January 2nd 2011, 12:42 AM

you've taken $\sum_{k\geq0} \rightarrow \sum_{k=0}^n$ but doesn't it has to be $\sum_{k\geq0} \rightarrow \sum_{k=0}^{n/2}$ that is because when $2k>n$ , $\binom{n}{2k}=0$ so the largest value that k can have is $\frac{n}{2}$ . if this is correct, since k is an integer, n has to even.

**BAdhi** · January 2nd 2011, 01:48 AM

forget what i've mentioned in my previous post it's all wrong and really sorry abount it.(because n is a given value it can either be odd or even)

but check out this method. Hope it's not wrong too.

$(a+b)^n=\sum_{r=0}^n\binom{n}{r}a^rb^{n-r}$

if n is odd

if a=1,b=-1

$0=\sum_{r=0}^n\binom{n}{2r}-\sum_{r=0}^n\binom{n}{2r+1}$ ___ (1)

if a=b=1;

$2^n=\sum_{r=0}^n\binom{n}{2r}-\sum_{r=0}^n\binom{n}{2r+1}$ ___(2)

by (1)+(2) i think we'll get the result for odd n

when n is even, same 2 equations could be achieved.

Thread: Even vs. Odd in a combinatoric proof

LinkBack

Thread Tools

Display

Even vs. Odd in a combinatoric proof

correction to the previous post

Similar Math Help Forum Discussions

Two combinatoric problems

Need help with Combinatoric Proof

combinatoric thing

Combinatoric sequence, please help me

combinatoric identity

Search Tags