# Thread: Parity proof with binomial coefficients

1. ## Parity proof with binomial coefficients

Hello,
let's assume the following set:
$\displaystyle Q_n = \{(x_1, x_2,...,x_n) \in \mathbb{R}^n | x_i \in \{0, 1, 2, 3\} \ \forall i \}$.

Vector $\displaystyle (x_1, x_2,...,x_n)$ in the set $\displaystyle Q_n$ is even, if the integer $\displaystyle 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 $\displaystyle Q_n$ are even.

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

Question is, how to do that with binomial coefficients. Any help is appreciated. Thank you!

2. 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, $\displaystyle (x_1,x_2,x_3,x_4)$. The total number of those vectors is $\displaystyle 4^4=256$. Then, any even vector can have 0, 2, or 4 odd entries. Here are the cases:

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

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

4 odd entries: $\displaystyle \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 $\displaystyle 2^4=16$ choices of elements. Similarly, for 2 odd entries, there are $\displaystyle 2^2\cdot 2^2=16$ choices, and for 4 odd entries, there are $\displaystyle 2^4=16$ choices.

In summary, there are

$\displaystyle \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 $\displaystyle n$ is arbitrary.