# Parity proof with binomial coefficients

• Jan 24th 2011, 10:00 AM
Greg98
Parity proof with binomial coefficients
Hello,
let's assume the following set:
$Q_n = \{(x_1, x_2,...,x_n) \in \mathbb{R}^n | x_i \in \{0, 1, 2, 3\} \ \forall i \}$.

Vector $(x_1, x_2,...,x_n)$ in the set $Q_n$ is even, if the integer $x_1+x_2+...+x_n$ is even, else vector is odd. The problem is to show using binomial coefficients, that half of the vectors in set $Q_n$ are even.

It's easy to see that for $n=1$, there's two combinations of four, which are even. Arbitrary $n=k$:
For $x_1+x_2+...+x_{k-1} \ \frac{1}{2}$ are even.
So, with $+x_k$ we get $\frac{2}{4}=\frac{1}{2}$.

Question is, how to do that with binomial coefficients. Any help is appreciated. Thank you!
• Jan 24th 2011, 12:57 PM
roninpro
There is only one condition required for a vector to be even: an even number of entries are odd.

For a solid example, consider vectors with four entries, $(x_1,x_2,x_3,x_4)$. The total number of those vectors is $4^4=256$. Then, any even vector can have 0, 2, or 4 odd entries. Here are the cases:

0 odd entries: $\displaystyle \binom{4}{0}=1$ arrangements

2 odd entries: $\displaystyle \binom{4}{2}=6$ arrangements

4 odd entries: $\displaystyle \binom{4}{4}=1$ arrangements

But take note that there are some degrees of freedom with each situation. For example, in the case of 0 odd entries, there are no choices for odd entries, but 2 choices for even. Therefore, there are $2^4=16$ choices of elements. Similarly, for 2 odd entries, there are $2^2\cdot 2^2=16$ choices, and for 4 odd entries, there are $2^4=16$ choices.

In summary, there are

$\displaystyle \binom{4}{0}\cdot 2^4+\binom{4}{2}\cdot (2^2\cdot 2^2)+\binom{4}{4}\cdot 2^4=128$

even vectors. This is exactly half of the total number of vectors.

Try to generalize this argument for the case where $n$ is arbitrary.