Maths Olympiad Prep

Library / /34 of 37

Number theory Difficulty 7.3 National olympiad, round 2 Find the answer

Determine all integers kk such that there exists infinitely many positive integers nn [b]not[/b] satisfying
n+k(2nn)n+k |\binom{2n}{n}

A number or a short expression. Spacing and $ signs are ignored.

Solution

Determine all integers k k such that there exist infinitely many positive integers n n not satisfying
n+k(2nn). n + k \mid \binom{2n}{n}.

We claim that all integers k1 k \neq 1 satisfy the desired property.

First, recall that 1n+1(2nn)\frac{1}{n + 1} \binom{2n}{n} is the n n -th Catalan number. Since the Catalan numbers are a sequence of integers, it follows that n+1(2nn) n + 1 \mid \binom{2n}{n} for all n n . Hence, k=1 k = 1 certainly cannot satisfy the problem statement.

Now, we consider two cases:

**Case 1: k2 k \neq 2 .**

Suppose that p p is a prime divisor of k k and let n=pα n = p^\alpha for any αN \alpha \in \mathbb{N} . Then, since pn+k p \mid n + k , in order to prove that n+k(2nn) n + k \nmid \binom{2n}{n} , it suffices to show that
p(2nn)=(n+1)(n+2)(2n)12n. p \nmid \binom{2n}{n} = \frac{(n + 1)(n + 2) \cdots (2n)}{1 \cdot 2 \cdots n}.
Note that the greatest power of p p that divides any term in the numerator or denominator of (n+1)(n+2)(2n1)12(n1)\frac{(n + 1)(n + 2) \cdots (2n - 1)}{1 \cdot 2 \cdots (n - 1)} is less than pα p^{\alpha} . Since the sets {1,2,,n1}\{1, 2, \cdots, n - 1\} and {n+1,n+2,,2n1}\{n + 1, n + 2, \cdots, 2n - 1\} are congruent modulo pα p^{\alpha} , the numerator and denominator of the fraction (n+1)(n+2)(2n1)12(n1)\frac{(n + 1)(n + 2) \cdots (2n - 1)}{1 \cdot 2 \cdots (n - 1)} both contain the same number of factors of p p . Therefore, p(n+1)(n+2)(2n1)12(n1) p \nmid \frac{(n + 1)(n + 2) \cdots (2n - 1)}{1 \cdot 2 \cdots (n - 1)} .

Now, if we can show that p2 p \nmid 2 , we will be able to conclude that p(2nn) p \nmid \binom{2n}{n} , as desired. Indeed, if p2 p \neq 2 , then trivially p2 p \nmid 2 . Meanwhile, if p=2 p = 2 , then let us take α2 \alpha \geq 2 so that 22n+k 2^2 \mid n + k . Hence, we wish to show that 22(2nn) 2^2 \nmid \binom{2n}{n} . But since 2(n+1)(n+2)(2n1)12(n1)=(2nn)2 2 \nmid \frac{(n + 1)(n + 2) \cdots (2n - 1)}{1 \cdot 2 \cdots (n - 1)} = \frac{\binom{2n}{n}}{2} , we need only show that 222 2^2 \nmid 2 , which is obvious. This concludes Case 1.

**Case 2: k=2 k = 2 .**

Seeking a nice expression for n+k n + k , we choose to set n=2α2 n = 2^{\alpha} - 2 for any αN \alpha \in \mathbb{N} with α2 \alpha \geq 2 . Then, since n+k=2α n + k = 2^{\alpha} , we wish to show that
2α(2nn)=(n+1)(n+2)(2n)12n. 2^{\alpha} \nmid \binom{2n}{n} = \frac{(n + 1)(n + 2) \cdots (2n)}{1 \cdot 2 \cdots n}.
Notice that since 2n<2α+1 2n < 2^{\alpha + 1} , the greatest power of 2 2 that divides any term in the numerator or denominator of (n+1)(n+2)(2n)12n\frac{(n + 1)(n + 2) \cdots (2n)}{1 \cdot 2 \cdots n} is 2α 2^{\alpha} . Then, because the sets {1,2,,n2}\{1, 2, \cdots, n - 2\} and {n+3,n+4,,2n}\{n + 3, n + 4, \cdots, 2n\} are congruent modulo 2α 2^{\alpha} , we deduce that 2(n+3)(n+4)(2n)12(n2) 2 \nmid \frac{(n + 3)(n + 4) \cdots (2n)}{1 \cdot 2 \cdots (n - 2)} . Removing this fraction from the fraction (2nn)=(n+1)(n+2)(2n)12n\binom{2n}{n} = \frac{(n + 1)(n + 2) \cdots (2n)}{1 \cdot 2 \cdots n}, it suffices to show that 2α(n+1)(n+2)(n1)n 2^{\alpha} \nmid \frac{(n + 1)(n + 2)}{(n - 1)n} . Keeping in mind that n+2=2α n + 2 = 2^{\alpha} , we see that the largest power of 2 2 that divides the numerator is 2α 2^{\alpha} , while the largest power of 2 2 that divides the denominator is 21 2^1 (since 2n 2 \mid n ). Therefore, 2α1 2^{\alpha - 1} is the largest power of 2 2 that divides (n+1)(n+2)(n1)n\frac{(n + 1)(n + 2)}{(n - 1)n}, so
2α(n+1)(n+2)(n1)n    n+k(2nn), 2^{\alpha} \nmid \frac{(n + 1)(n + 2)}{(n - 1)n} \implies n + k \nmid \binom{2n}{n},
as desired.

Thus, the integers k k that satisfy the condition are all integers k1 k \neq 1 .

The answer is: \boxed{k \neq 1}.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.