1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Straightforward Binomial Coefficient Proof

  1. Feb 7, 2012 #1
    1. The problem statement, all variables and given/known data

    Let n be an element of the positive numbers (Z+). Prove that 3 divides (3n n) or "3n choose n". Use the definition of a binomial coefficient to solve.

    2. Relevant equations

    Definition of a Binomial Coefficient: (n k) := ( n! / k!(n - k)! )

    3. The attempt at a solution

    I've done the basics. I've replaced n and k with 3n and n, making the equation: (3n n) = ( 3n! / n!(3n - n)! ), then simplifying to ( 3n! / n!(2n)! ), which equals just ( 3 / 2n! ).

    If it is divisible by 3, I suppose this can be expressed as: (( 3 / 2n! )) / 3 = k, and therefore, ( 3 / 2n! ) = 3k . It seems like the real proof here is in showing that 2n! is an integer.

    How do I go forward?
  2. jcsd
  3. Feb 7, 2012 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    See what happens when you are not careful to use brackets? You obtain the nonsensical "result" [tex] C(3n,n) = \frac{3}{2n!},[/tex]
    which is just about as wrong as it can be. You need to write
    [tex] C(3n,n) = \frac{(3n)!}{n! (2n)!} = \frac{3n (3n-1) \cdots (2n+1)}{n!}. [/tex]
    So, you need to show that
    [tex]N = \frac{n (3n-1) \cdots (2n+1)}{n!} [/tex]
    is an integer.

    Alternatively, you can use induction on n.

    Last edited: Feb 7, 2012
  4. Feb 8, 2012 #3
    Thanks, Ray.

    I've been trying to prove what you stated in N, and I realize that a factorial is a set of integers which are multiplied together and whose result is an integer. Because dividing an integer by another integer doesn't necessary yield an integer, my approach to this is removing the denominator. I can't seem to do this, however.

    I'm stuck at N = ( n (3n-1) (3n-2) ... (2n+2) (2n+1) ) / n!

    How do I get rid of the n! ? Any help is appreciated.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook