Author |
Topic: Certain Composite Catalans (Read 397 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Certain Composite Catalans
« on: Jun 13th, 2007, 6:38pm » |
 Quote  Modify
|
If n = 3 (mod 6),
prove/disprove:
The nth Catalan number, C(2n,n)/(n+1), is divisible by n+2.
(C(n,k) = n choose k, number of ways of selecting k objects from n objects)
|
| « Last Edit: Jun 13th, 2007, 6:44pm by Aryabhatta » |
 IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Certain Composite Catalans
« Reply #1 on: Jun 20th, 2007, 3:04pm » |
Quote Modify
|
Before I forget...
I think we can prove it, using the below repeatedly
i) if (a,b) = 1 and if ax and bx are both integers, then x is an integer.
ii) if N +1 = a + b and (a,b) = 1 then N! is divisible by a! * b! (follows from i)
|
| « Last Edit: Jun 20th, 2007, 3:04pm by Aryabhatta » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Certain Composite Catalans
« Reply #2 on: Jun 20th, 2007, 9:34pm » |
Quote Modify
|
It helps to first show that Cn = C(2n,n)/(n+1) is an integer: | hidden: | (2n+1)C(2n,n) = (n+1)C(2n+1,n), and since n+1, 2n+1 are relatively prime, n+1 divides C(2n,n).
Similarly, (2n+2)(2n+1)Cn = (n+2)C(2n+2,n), so n+2 divides Cn if n+2 is relatively prime to 2n+1 and 2n+2. (n+2, 2n+2) = (n+2, 2) = 1 iff n is odd, and (n+2, 2n+1) = (n+2, 3) = 1 iff n is either 0 or 2 mod 3. So n+2 | Cn whenever n is 3 or 5 mod 6. |
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Certain Composite Catalans
« Reply #3 on: Jun 21st, 2007, 10:20am » |
Quote Modify
|
Nice!
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print