Results 1 to 2 of 2

Math Help - Parity proof with binomial coefficients

  1. #1
    Junior Member Greg98's Avatar
    Joined
    Oct 2009
    From
    Brugge, BEL
    Posts
    39

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Proof about parity of a set of four integers
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 5th 2010, 06:26 PM
  2. Proof of a series with binomial coefficients
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 25th 2010, 09:08 PM
  3. Sums of Binomial Coefficients - proof by induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 22nd 2010, 08:44 AM
  4. Binomial coefficients 3
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 30th 2009, 12:02 PM
  5. Binomial coefficients
    Posted in the Algebra Forum
    Replies: 2
    Last Post: February 13th 2009, 01:22 PM

Search Tags


/mathhelpforum @mathhelpforum