# Straightforward Binomial Coefficient Proof

1. Feb 7, 2012

### DonOMazzetti

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. Feb 7, 2012

### Ray Vickson

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

Alternatively, you can use induction on n.

RGV

Last edited: Feb 7, 2012
3. Feb 8, 2012

### DonOMazzetti

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.