Prove that for all odd n>1, we have 8n+4|C4n2n.
Problem
Source: Indonesia TST 2009 First Stage Test 1 Problem 1
Tags: induction, modular arithmetic, number theory, number theory proposed
27.12.2008 16:42
We have C2n4n=(4n)!(2n)!(2n)!=(2n+1)⋅(2n+2)⋯(4n)(2n)! is divisble by (2n+1). But it is easy to see that 4|C2n4n, therefore we are done.
27.12.2008 17:33
N.T.TUAN wrote: We have (2n+2)⋯(4n)(2n)! I think you must prove this number is an integer . An other approach : \frac{{{4n} \choose {2n}}}{2n+1}={{4n}\choose {2n}}-{{4n}\choose{2n+1}} ,thus it must be integer . v_2((4n)!)={4n-S(4n)}=4n-S(n) v_2((2n!)^2)=2(2n-S(2n))=2(2n-S(n)) where S(n) is some digit of n when written in base 2. Because n is odd and n is great than 1 so S(n)\geq 2 . Thus 4|(\frac{4n}{2n}) . Note : In this problem I have used an old result in number theory . v_p(n!)=\frac{n-S_p(n)}{p-1} where v_p(n) is the exponent of p and S_p(n) is sum digits of n in base p .
29.12.2008 10:39
TTsphn wrote: I think you must prove this number is an integer . An other approach But it is easy.
24.01.2009 22:01
Dear N T TUAN How can we prove easy \dfrac{(2n + 2)\cdots (4n)}{(2n)!} is an integer?
25.01.2009 23:21
N.T.TUAN wrote: We have C_{4n}^{2n} = \frac {(4n)!}{(2n)!(2n)!} = (2n + 1)\cdot \dfrac{(2n + 2)\cdots (4n)}{(2n)!} is divisble by (2n + 1). But it is easy to see that 4|C_{4n}^{2n}, therefore we are done. Nice, but i see a typo C^{2n}_{4n}\not= C^{4n}_{2n} To mayhem: Try induction to prove that \dfrac{(2n+2)\cdot...\cdot (4n)}{(2n)!} is an integer
26.01.2009 01:03
TTsphn wrote: N.T.TUAN wrote: We have \dfrac{(2n + 2)\cdots (4n)}{(2n)!} I think you must prove this number is an integer . But this is just a Catalan number! Vikernes: was that a joke? It's common notation in some countries.
26.01.2009 01:24
t0rajir0u wrote: Vikernes: was that a joke? It's common notation in some countries. He means that some people denote \binom{a}{b} by C_a^b, while others call it C_b^a (though all books I know use C_a^b only, but I have seen both notations on MathLinks - maybe the second one is a mistake every time it is posted). Anyway, there is no reason to use the C notation on the internet - we have enough space here. darij
26.01.2009 01:32
t0rajir0u wrote: Vikernes: was that a joke? It's common notation in some countries. Mmm i know that C^{n}_{k}=\binom{n}{k}, but i thought that C^{2n}_{4n}=\binom{2n}{4n} also.
27.01.2009 07:01
I mean that C_n^k=\frac{n!}{k!(n-k)!}.
05.02.2009 19:10
WOW!! beautiful fact that v_p(n!) = \frac {n - S_p(n)}{p - 1} I didn't know that. SO I try this by lucas' theorem by lucas' theorem {{2m} \choose {2k}} \equiv {{m} \choose {k}}\pmod {2} {{2m} \choose {2k + 1}} \equiv 0 \pmod {2} {{4n} \choose {2n}} = 2^{4n} - 2({{4n} \choose {0}} + {{4n} \choose {1}} + \cdots + {{4n} \choose {2n - 1}}) now we show {{4n} \choose {0}} + {{4n} \choose {1}} + \cdots {{4n} \choose {2n - 1}} \equiv 0 \pmod {2} {{4n} \choose {0}} + {{4n} \choose {1}} + \cdots {{4n} \choose {2n - 1}} \equiv {{2n} \choose {0}} + {{2n} \choose {1}} + \cdots + {{2n} \choose {n - 1}} \equiv {{n} \choose {0}} + {{n} \choose {1}} + \cdots + {{n} \choose {\frac {n - 1}{2}}} \equiv 2^{n - 1} \equiv 0\pmod {2}
01.05.2009 07:09
let \frac {(2n + 2)\cdot...\cdot (4n)}{(2n)!} = k then (2n + 1)k = C^{4n}_{2n} \in Z also (4n + 1)k = C^{4n + 1}_{2n} \in Z \Longrightarrow 2(2n + 1)k - (4n + 1)k = k \in Z
01.05.2009 07:35
Catalan number Ca_{2n}=\frac{1}{2n+1}C_{4n}^{2n}\in N
31.05.2010 11:21
C_{4n}^{2n}=\frac{4n!}{2n!(2n)!} it divides to 2n+1 it's enough to show that C_{4n}^{2n} divides by 4
31.05.2010 11:25
mayhem wrote: Dear N T TUAN How can we prove easy \dfrac{(2n + 2)\cdots (4n)}{(2n)!} is an integer? hi, C_n^k means that in how many ways we can chose k pencils from n pencils, that's why it is integer and also positive, but by number theory sorry, I don't know........