Results 1 to 3 of 3

Math Help - Proof Help

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Proof Help

    Prove that for all K > 0, (2k choose k) is an even number.

    Any advice?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by jzellt View Post
    Prove that for all K > 0, (2k choose k) is an even number.

    Any advice?
    The sum of all the binomial coefficients (n choose j), as j goes from 0 to n, is 2^n, which is even. The coefficients pair off, with (n choose j) = (n choose n–j), and obviously the sum of each pair is even. If n=2k is even, there is a "left-over" term (2k choose k), in the middle of the sequence, which does not pair off with another term. In order for the sum of the whole sequence to be even, this term must clearly be even.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2008
    Posts
    148
    {2k \choose k} = \frac{(2k)!}{k!(2k-k)!} = \frac{(2k)!}{(k!)^2}.

    For k=1 the assertion is true.

    (2k)! = 2 \cdot 3 \cdot \mathellipsis \cdot k \cdot (k+1) \mathellipsis 2k and (k!)^2 = (2 \cdot 3 \cdot \mathellipsis \cdot k)(2 \cdot 3 \cdot \mathellipsis \cdot k)

    Cancelling where possible we have:

    \frac{(2k)!}{(k!)^2} = \frac{(k+1)(k+2) \mathellipsis 2k}{(2 \cdot 3 \cdot \mathellipsis \cdot k)}.

    Now the power of 2 in the prime factorization of (k+1)(k+2) \mathellipsis 2k is exactly k (easy proof by induction). But the power of 2 in the prime factorization of (2 \cdot 3 \cdot \mathellipsis \cdot k) is less than k (another easy proof by induction) and therefore the quotient must be even.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: October 19th 2010, 11:50 AM
  2. Replies: 0
    Last Post: June 29th 2010, 09:48 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 11:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 05:07 PM

Search Tags


/mathhelpforum @mathhelpforum