Straightforward Binomial Coefficient Proof

  • #1

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?
 

Answers and Replies

  • #2
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,722

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

RGV
 
Last edited:
  • #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.
 

Related Threads on Straightforward Binomial Coefficient Proof

Replies
2
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
2
Views
3K
Replies
3
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
792
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
890
Replies
2
Views
1K
  • Last Post
Replies
3
Views
3K
Top