Even and Odd Entries in Pascal's Triangle

Problem

Let $a_1, a_2, .. a_n$ each be an element of the set $\{1, -1\}$.

When the product $a_1 a_2 .. a_n$ equals $1$, how many such combinations of $a_1, a_2, .. a_n$ are there?

Solution 1

If we choose the first $n-1$ entries freely, then the condition $a_1 a_2 .. a_n = 1$ uniquely determines whether $a_n$ is $1$ or $-1$.

Thus, the number of combinations equals the number of free choices of $a_1, a_2, .. a_{n-1}$, which is $2^{n-1}$.

Solution 2

From the condition $a_1 a_2 .. a_n = 1$, the number of $-1$’s must be even. Counting the cases with $0, 2, \ldots$ minus ones, we get

$$ \sum^{n}_{k:even} \binom{n}{k} $$

combinations. By the binomial theorem,

$$ (1-1)^n = \sum^{n}_{k=0} \binom{n}{k} (-1)^k = \sum_{k:even}^{n} \binom{n}{k} - \sum_{k:odd}^{n} \binom{n}{k} = 0 $$

Therefore,

$$ \sum_{k:even}^{n} \binom{n}{k} = \sum_{k:odd}^{n} \binom{n}{k} $$

Hence

$$ \sum_{k:even}^{n} \binom{n}{k} = \frac{\sum_{k=0}^{n} \binom{n}{k}}{2} $$

Again by the binomial theorem,

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

so

$$ \sum_{k:even}^{n} \binom{n}{k} = \frac{2^n}{2} = 2^{n-1} $$

combinations.

Solution 3

This is the same as Solution 2, but we evaluate

$$ \sum_{k:even}^{n} \binom{n}{k} $$

in a different way.

If $n$ is odd and can be written as $2m + 1$, then the sum is

$$ \binom{2m+1}{0} + \binom{2m+1}{2} + \binom{2m+1}{4} + … + \binom{2m+1}{2m} $$

Applying

$$ \binom{n}{k} = \binom{n}{n-k} $$

to each term gives

$$ \binom{2m+1}{2m+1} + \binom{2m+1}{2m-1} + \binom{2m+1}{2m-3} + … + \binom{2m+1}{1} $$

which is exactly the sum of the odd-indexed entries in reverse order.

Therefore,

$$ \sum_{k:even}^{n} \binom{n}{k} = \sum_{k:odd}^{n} \binom{n}{k} $$

This is immediate if you look at an odd-numbered row of Pascal’s triangle.

When $n$ is even and written as $2m$, look at the odd-numbered row immediately above and use

$$ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} $$

Then

$$ \binom{2m}{2} + \binom{2m}{4} + … + \binom{2m}{2m-2} = \binom{2m-1}{1} + \binom{2m-1}{2} + \binom{2m-1}{3} + \binom{2m-1}{4} … + \binom{2m-1}{2m-2} $$

Furthermore, adding

$$ \binom{2m}{0} = \binom{2m-1}{0} $$

$$ \binom{2m}{2m} = \binom{2m-1}{2m-1} $$

to both sides yields

$$ \sum_{k:even}^{n} \binom{n}{k} = \sum_{k=0}^{n-1} \binom{n-1}{k} = 2^{n-1} $$

so the same relation holds for even-numbered rows as well.

One can prove the odd-row case in the same way as the even-row case; for odd rows, however, symmetry in Pascal’s triangle makes it immediate (one is simply adding the same quantities), whereas even rows need an extra argument, which is why the proof is arranged this way here.