Prove $\binom{n}{0}$ + $\binom{n}{2}$ + $\binom{n}{4} + ...+\binom{n}{n-1}=\binom{n}{1}+\binom{n}{3}+\binom{n}{5}+...+\binom{n}{n}$

Question

I want to prove that $\binom{n}{0}$ + $\binom{n}{2}$ + $\binom{n}{4} + ...+\binom{n}{n-1}=\binom{n}{1}+\binom{n}{3}+\binom{n}{5}+...+\binom{n}{n}$ for all odd numbers $n \ge 1$

I see that $\binom{n}{0}$ and $\binom{n}{n}$ are both equal to $1$ and therefor remove each other.

But what can I do after that? I'm very lost, please help me move in the right direction at least.

Answer 1

You can prove by induction on $n$ that $$\sum_{k} (-1)^k \binom{n}{k} =0$$ for all $n\ge 1$. For $n=1$ it's easy to check. Assume that it's true for some $n\ge 1$. Denote by $a_k = \binom{n}{k}$, $a_k'= \binom{n+1}{k}$. So we have $$\sum_{k}(-1)^k a_k = 0$$ and want to show that $$\sum_{k} (-1)^k a_k'=0$$ We have (Pascal triangle) $$a_{k}' = a_k+ a_{k-1}$$ Now break the sum $\sum_k (-1)^k a_k'$ into two sums.

$\bf{Added:}$ In a similar way one proves by induction on $n$ that $$\sum_k \binom{n}{k} = 2^n$$ or even $$\sum_k x^k \binom{n}{k} = (1+x)^n$$

Answer 2

Here's an intuitive combinatorial proof. The left-hand side is the number of even-sized subsets of an $n$-set, which we'll call $X$. The right-hand side is the number of odd-sized subsets of $X$. But $Y \mapsto X \setminus Y$ is a $1$-$1$ mapping of even-sized subsets onto odd-sized subsets, so the two numbers must be equal.