# Math Help - Proof with Combinations

1. ## Proof with Combinations

I've been having trouble with the following proof:

Let n be an odd positive integer. Prove that

$\binom{n}{0}$ + $\binom{n}{2}$ + $\binom{n}{4}$ + ... + $\binom{n}{n-1}$ = $2^{n-1}$

My first attempt at a proof was to use induction but at the inductive step, I couldn't simplify it to work out. After consulting my professor, he said that while it possible to prove it by induction, he could think of numerous other ways without induction. I'm not too sure of what to do now.

2. Originally Posted by icecube
I've been having trouble with the following proof:

Let n be an odd positive integer. Prove that

$\binom{n}{0}$ + $\binom{n}{2}$ + $\binom{n}{4}$ + ... + $\binom{n}{n-1}$ = $2^{n-1}$

My first attempt at a proof was to use induction but at the inductive step, I couldn't simplify it to work out. After consulting my professor, he said that while it possible to prove it by induction, he could think of numerous other ways without induction. I'm not too sure of what to do now.

Remember Newton's Binomial Theorem: $(a+b)^n=\sum_{k=0}^n\left(\begin{array}{c}n\\k\end {array}\right)a^{n-k}b^k$

Also, note that $1^n=1$ for any power n
Tonio

3. Well I tried using Binomial Theorem, and using (1+1)^(d-1) and other variations, however, I could not prove that the terms from the Binomial Theorem were the same as in the proposition.

4. Originally Posted by icecube
Well I tried using Binomial Theorem, and using (1+1)^(d-1) and other variations, however, I could not prove that the terms from the Binomial Theorem were the same as in the proposition.
Can you see why for odd n,

$\binom{n}{0} + \binom{n}{2} + ... + \binom{n}{n-1} = \binom{n}{1} + \binom{n}{3} + ... + \binom{n}{n}$ ?

5. Yes I can see why for odd n that would hold true. (I expanded each combination and saw that the terms were equal in reverse order).

Now I just have to see how I can use this to relate my proof to the Binomial Theorem (?).

EDIT: Oh wait. Hm...

$
\binom{n}{0} + \binom{n}{2} + ... + \binom{n}{n-1} = \binom{n}{1} + \binom{n}{3} + ... + \binom{n}{n} = 2^{n-1} = \frac{2^{n}}{2}$

$\binom{n}{0} + \binom{n}{2} + ... + \binom{n}{n-1} + \binom{n}{1} + \binom{n}{3} + ... + \binom{n}{n} = 2^{n} = (1+1)^{n} = \sum_{k=0}^n \binom{n}{k} 1^{n-k}1^{k}
$

The proof is basically complete since the terms of each series are exactly equal. Is this correct?

6. Originally Posted by icecube
Yes I can see why for odd n that would hold true. (I expanded each combination and saw that the terms were equal in reverse order).

Now I just have to see how I can use this to relate my proof to the Binomial Theorem (?).

EDIT: Oh wait. Hm...
$
\binom{n}{0} + \binom{n}{2} + ... + \binom{n}{n-1} = \binom{n}{1} + \binom{n}{3} + ... + \binom{n}{n} = 2^{n-1} = \frac{2^{n}}{2}$

$\binom{n}{0} + \binom{n}{2} + ... + \binom{n}{n-1} + \binom{n}{1} + \binom{n}{3} + ... + \binom{n}{n} = 2^{n} = (1+1)^{n} = \sum_{k=0}^n \binom{n}{k} 1^{n-k}1^{k}
$

Is this correct?
That is pretty much correct. A more clear way of showing it would be:

$2^n = (1+1)^n = \sum_{k=1}^n\binom{n}{k}1^n1^{n-k} = \binom{n}{0} + \binom{n}{1} + ... + \binom{n}{n-1} + \binom{n}{n} =$ $2(\binom{n}{0} + \binom{n}{2} + ... + \binom{n}{n-1}) = 2^n \Rightarrow \frac{2^n}{2} = \boxed{2^{n-1} = \binom{n}{0} + \binom{n}{2} + ... + \binom{n}{n-1}}$

7. Ah, yes my work tends to be a bit disorganized XD. Thank you so much! Now to write it up x_x.