TAOCP 1.2.6 Exercise 37
By Exercise 36 and the binomial theorem (13), \sum_k \binom{n}{k} = (1+1)^n = 2^n, and
Section 1.2.6: Binomial Coefficients
Exercise 37. [M10] From the answers to the preceding exercise, deduce the value of the sum of every other entry in a row, $\binom{n}{0} + \binom{n}{2} + \binom{n}{4} + \cdots$.
Verified: no
Solve time: -
By Exercise 36 and the binomial theorem (13),
$$ \sum_k \binom{n}{k} = (1+1)^n = 2^n, $$
and
$$ \sum_k \binom{n}{k}(-1)^k = (1-1)^n = 0 \qquad (n>0). $$
Let
$$ E=\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots, $$
and let
$$ O=\binom{n}{1}+\binom{n}{3}+\binom{n}{5}+\cdots. $$
Then
$$ E+O=2^n, $$
while
$$ E-O=0. $$
Adding these equations gives $2E=2^n$, hence
$$ E=2^{n-1} \qquad (n>0). $$
For $n=0$, the sum is $\binom00=1$. Therefore
$$ \boxed{\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots = 2^{n-1}\quad (n>0).} $$