Straightforward Binomial Coefficient Proof

[DonOMazzetti]

Homework Statement

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.

Homework Equations

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

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?

 

[Ray Vickson]

Homework Statement

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.

Homework Equations

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

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?

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

 

[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.