Maths Olympiad Prep

Library / /291 of 462

Combinatorics Difficulty 6.1 National Olympiad Prove it Ireland

For each positive integer nn, let
Cn=1n+1(2nn), C_n = \frac{1}{n+1} \binom{2n}{n},
where, as usual,
(2nn)=(2n)!(n!)2. \binom{2n}{n} = \frac{(2n)!}{(n!)^2}.
(i) Prove that CnC_n is an integer for every positive integer nn.
(ii) Prove that CnC_n is not a prime number if n>3n > 3.

Solution

Observe first that
(2n+1n)=(2n+1)((2n)!)n!(n+1)!=(2n+1)Cn, \binom{2n+1}{n} = \frac{(2n+1)((2n)!)}{n!(n+1)!} = (2n+1)C_n,
so
Cn=(2n+2(2n+1))Cn=2(2nn)(2n+1n), C_n = (2n + 2 - (2n + 1))C_n = 2 \binom{2n}{n} - \binom{2n+1}{n},
so CnC_n is an integer, as all binomial coefficients (mk)\binom{m}{k} with positive integers m,km, k with kmk \le m are integers. This establishes (i).

To prove (ii), note that
Cn+1=1n+2(2n+2n+1)=(2n+2)(2n+1)((2n)!)(n+2)((n+1)!)2=2(2n+1)n+2Cn, C_{n+1} = \frac{1}{n+2} \binom{2n+2}{n+1} = \frac{(2n+2)(2n+1)((2n)!)}{(n+2) \cdot ((n+1)!)^2} = \frac{2(2n+1)}{n+2} C_n,
hence
(n+2)Cn+1=2(2n+1)Cn.(1) (n + 2)C_{n+1} = 2(2n + 1)C_n. \qquad (1)
By definition
Cn=1n+1(2nn)=2n(2n1)(n+1)(n+1)n(n1)21=(2n1)(2n2)(n+3)(n+2)(n1)3 \begin{aligned} C_n &= \frac{1}{n+1} \binom{2n}{n} = \frac{2n(2n-1)\cdots(n+1)}{(n+1)n(n-1)\cdots2 \cdot 1} \\ &= \frac{(2n-1)(2n-2)\cdots(n+3)(n+2)}{(n-1)\cdots3} \end{aligned}

Thus, for n>3n > 3,
n+2Cn=(n1)(n2)3(2n1)(2n2)(n+3)<1, \frac{n+2}{C_n} = \frac{(n-1)(n-2)\cdots3}{(2n-1)(2n-2)\cdots(n+3)} < 1,
since each factor hh in the numerator is matched by a factor h+nh+n in the denominator. Thus CnC_n does not divide n+2n+2.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.