Originally Posted by

**icecube** I've been having trouble with the following proof:

Let n be an odd positive integer. Prove that

$\displaystyle \binom{n}{0}$ + $\displaystyle \binom{n}{2}$ + $\displaystyle \binom{n}{4}$ + ... + $\displaystyle \binom{n}{n-1}$ = $\displaystyle 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.