Author |
Topic: Binomial coefficient divisibility (Read 761 times) |
|
NickH
Senior Riddler
Gender: 
Posts: 341
|
 |
Binomial coefficient divisibility
« on: Apr 5th, 2003, 10:15am » |
 Quote  Modify
|
Show that the binomial coefficient 2nCn = (2n!) / (n!)2 is divisible by n+1.
|
|
 IP Logged |
Nick's Mathematical Puzzles
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Binomial coefficient divisibility
« Reply #1 on: Apr 14th, 2003, 8:13pm » |
Quote Modify
|
Normally, I would first try induction on something like this, but a quick induction attempt failed. However it did show that this number is even and divisible by 2N-1.
Can someone prove that it is divisible by N+1? It is evidently true when N+1 is prime because the expression equals (N+1)(N+2)...(N+N)/1/2/...N, and when N is prime nothing in the denominator will divide out the factor of N+1.
The formula represents the number of ways N pennies and N dimes can be arranged in a row of 2N coins. Does being divisible by N+1 mean there is a systematic way of listing those permutations that divides into N+1 equal sized groups? Of course, if the problem is true then the list can be split into N+1 groups, but I mean such that there is a pattern in common with the 1st, 2nd, ... permutation in each group. Sort of like (2N!)/N!/N! is obviously even because for each permutation there is a corresponding one obtained by switching the pennies and dimes.
|
|
IP Logged |
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Binomial coefficient divisibility
« Reply #2 on: Apr 15th, 2003, 2:41pm » |
Quote Modify
|
I seem to have had similar problems to you before I gave up. I could not prove that the denominator would not divide out the numerator N+1 term and decided to leave to some of the others better at math.
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Binomial coefficient divisibility
« Reply #3 on: Apr 15th, 2003, 7:37pm » |
Quote Modify
|
It is obviously true as (2n)Choose(n) / n+1 is the nth Catalan number.
SWF, you might find some inspiration at http://mathworld.wolfram.com/CatalanNumber.html
|
| « Last Edit: Apr 15th, 2003, 8:07pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
LZJ
Junior Member
Gender:
Posts: 82
|
|
Re: Binomial coefficient divisibility
« Reply #4 on: Apr 17th, 2003, 9:00pm » |
Quote Modify
|
I have a way to prove this (I think): (sorry, don't really know how to use towr's formula generator yet)
2nCn can be expressed as the summation, from (r = 0) to (r = n - 1), of (n+1Cr+1)(n-1Cr).
From here, we find that 2nCn can be further simplified to be expressed as the summation of
(n+1) * nCr*nCr+1 / (n)
Now, we have to prove that nCr*nCr+1 is divisible by n.
If n is prime, the solution is trivial. If n is non-prime, however, it can be expressed as the product of its smallest prime factor and another number.
For example: n = a * b, where a is its smallest prime factor.
nCr*nCr+1 can be expressed as
(n!)2 / (r)!(r+1)!(n-r)!(n-r-1)!
Looking at the denominator, we find that the maximal power of b is 3, whereas in the numerator, the minimal power of b is 4 (when a = 2, for example). => b4 / b3
Furthermore, the minimal power of a in the numerator will be greater than the maximal power of a in the denominator, therefore nCr*nCr+1 is divisible by n since it is divisible by a and b.
Since 2nCn can be expressed as the summation of
(n+1) * nCr*nCr+1 / (n), from r = 0 to r = n - 1,
and nCr*nCr+1 / (n) is an integer, therefore
2nCn is divisible by n + 1.
|
|
IP Logged |
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: Binomial coefficient divisibility
« Reply #5 on: Apr 18th, 2003, 2:24pm » |
Quote Modify
|
Here's a hint as to an easier way to derive this result. It shows a way to derive SWF's result, that 2nCn is divisible by 4n-2, using the fact that 2nCn is divisible by n+1.
Consider n / [2n(2n-1)] * 2nCn = (2n-2)! / [(n-1)! n!] = 2n-2Cn-1 / n, an integer.
<added>To clarify for LZJ, below, yes, we still need to prove 2nCn is divisible by n+1. The above proof contains a hint as to how to do that.</added>
|
| « Last Edit: Apr 18th, 2003, 7:40pm by NickH » |
IP Logged |
Nick's Mathematical Puzzles
|
|
|
LZJ
Junior Member
Gender:
Posts: 82
|
|
Re: Binomial coefficient divisibility
« Reply #6 on: Apr 18th, 2003, 7:30pm » |
Quote Modify
|
Don't you still have to prove that 2n-2Cn-1/n is an integer? Or perhaps you are saying it can be used after proving that 2nCn is divisible by 4n-2 ?
I admit that my method is somewhat inelegant, but then, "when in doubt, use brute force". 
|
| « Last Edit: Apr 18th, 2003, 7:31pm by LZJ » |
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Binomial coefficient divisibility
« Reply #7 on: Apr 26th, 2003, 9:07pm » |
Quote Modify
|
(2N)!/N!/N! = (N+1)*TN/N!, where TN is the product of the N-1 consecutive integers from N+2 to 2N. If TN/N! can be shown to be an integer, then the problem is solved.
For the product of a block of consecutive integers, consider how many of them are a multiple of pk for prime p and positive integer k. It will be shown that no matter the values p and k, the number of integers in the product for TN that are divisible by pk is never less than the count of such integers in N!. Therefore, TN/N! is an integer.
For any set of N consecutive integers, the number of them that are multiples of pk, cannot be fewer than count of them for N!. This is because such integers are equally spaced among the integers, and the first pk-1 integers in the product for N! are not multiples of pk.
Assuming (N+1) is not a multiple of pk, then TN cannot have fewer multiples of pk in its product than N!, because along with (N+1), that makes N consecutive integers.
In the case that (N+1) is a multiple of pk, that means the last pk-1 integers multiplied together in N! are not multiples of pk. So the number of multiples of pk in N! is the same as in (N-pk+1)!, which cannot be more than the number of multiples in the N-1 consecutive integers multipled to get TN because N-pk+1<=N-1.
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Binomial coefficient divisibility
« Reply #8 on: Apr 26th, 2003, 10:49pm » |
Quote Modify
|
2nCn
2nCn - ------
n + 1
n
= ------- . 2nCn
n + 1
= 2nCn-1
2nCn
Therefore -------- = 2nCn - 2nCn-1 QED
n + 1
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print