Show that ${n \choose 1} + {n \choose 3} +\cdots = {n \choose 0} + {n \choose 2}+\cdots$

Question

Show $${n \choose 1} + {n \choose 3} +\cdots = {n \choose 0} + {n \choose 2}+\cdots$$

A hint is given to consider the expansion $(x-y)^n$

However, when I plug in a number for $n$, I don't get an equality. $n=5$, for instance, I get $5+10 = 1 +10$.

How is this equality possible?

Answer 1

Hint: $$\begin{pmatrix} n \\ k\end{pmatrix} = \begin{pmatrix} n \\ n-k \end{pmatrix}.$$

Answer 2

Note that $$0=\{1+(-1)\}^n=\sum_{i=0}^{n}\binom{n}{i}\cdot 1^{n-i}\cdot (-1)^i.$$

Answer 3

You know that:

$$(x+y)^n=\sum_{i=0}^{n}x^iy^{n-i} {n \choose i}$$

If you substitute $x=1$ and $y=-1$ you get:

$$0=(1-1)^n=\sum_{i=0}^{n}1^i \cdot (-1)^{n-i} {n \choose i}$$

Next move elements with odd index to left.

Answer 4

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

Answer 5

The standard binomial expansion gives:

$$(x+y)^n=\sum_{r=0}^{n} \binom nr x^{n-r}y^r$$

Put $x=1, y=-1$: $$\begin{align} 0&=\sum_{r=0}^{n} \binom nr (-1)^r \\ &=\binom n0-\binom n1+\binom n2-\binom n3+\cdots +(-1)^n\binom nn\\ \binom n1+\binom n3+\binom n5+\cdots&=\binom n0+\binom n2+\binom n4\cdots\end{align}$$

It is interesting to consider some simple numerical examples of the expansion for different values of $n$ to get a more intuitive feel of the formula. A bar above the number indicates a negative sign.

$n=2$:

$$1\quad \bar{2}\quad 1$$

$n=3$:

$$1\quad \bar{3}\quad 3\quad \bar{1}$$

$n=4$:

$$1\quad \bar{4}\quad 6\quad \bar{4}\quad 1$$

$n=5$:

$$1\quad \bar{5}\quad 10\quad \overline{10}\quad 5\quad\bar{1}$$

From the above it is clear that:

• for odd $n$, a coefficient has the opposite sign of its "mirror image", i.e. $${n\choose k}=-{n\choose n-k}$$ (e.g. 1, -1; -3, 3) thus cancelling out pairwise.

• for even $n$, this does not occur as a coefficient has the same sign as its "mirror image" (e.g. 1, 1; -4, -4); however, the sum of coefficients in even positions is numerically equal to the sum of coefficients in odd positions, but is negative, thus the sums cancel out (e.g. 1+6+1=4+4, and (1+6+1)+(-4-4)=0)

Thus the formula holds for both odd and even $n$.

Answer 6

If you flip a fair coin $n\ge 1$ times. There are an equal probability, and hence an equal number of ways, of seeing an even number of heads as an odd number of heads. This is because after the first $n-1$ flips your heads parity is either even or odd, and on the $n^{th}$ flip there is a 50-50 chance of staying the same or changing.