Prove that for all odd $ n > 1$, we have $ 8n + 4|C^{4n}_{2n}$.
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 $ 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.
27.12.2008 17:33
N.T.TUAN wrote: We have $ \dfrac{(2n + 2)\cdots (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........