Maths Olympiad Prep

Library / /213 of 462

Combinatorics Difficulty 5.7 AIME, harder Prove it Ireland

Let nn be a positive integer and define
f(j)=(2jj)(2n2jnj),j=0,1,,n. f(j) = \binom{2j}{j} \cdot \binom{2n-2j}{n-j}, \quad j = 0, 1, \dots, n.
Prove that
(a) f(j)f(j+1)f(j) \ge f(j+1), if 0j<n/20 \le j < n/2;
(b) ff is strictly convex, i.e.,
f(j+1)+f(j1)>2f(j),j=1,2,,n1. f(j+1) + f(j-1) > 2f(j), \quad j = 1, 2, \dots, n-1.

Solution

Let uj=(2jj)u_j = \binom{2j}{j}, j=0,1,2,j = 0, 1, 2, \dots. For fixed n,jn, j we use the abbreviation m=njm = n-j to get f(j)=ujunj=ujumf(j) = u_j u_{n-j} = u_j u_m and f(j+1)=uj+1unj1=uj+1um1f(j+1) = u_{j+1} u_{n-j-1} = u_{j+1} u_{m-1}.

a.
Since
uj+1=2(2j+1)j+1ujandum=2(2m1)mum1, we have u_{j+1} = \frac{2(2j+1)}{j+1} u_j \quad \text{and} \quad u_m = \frac{2(2m-1)}{m} u_{m-1}, \text{ we have}
f(j)f(j+1)=ujumuj+1um1=2(2m1m2j+1j+1)uj+1um1=2((2m1)(j+1)(2j+1)mm(j+1))uj+1um1=2(mj1m(j+1))uj+1um10, \begin{align*} f(j) - f(j+1) &= u_j u_m - u_{j+1} u_{m-1} \\ &= 2 \left( \frac{2m-1}{m} - \frac{2j+1}{j+1} \right) u_{j+1} u_{m-1} \\ &= 2 \left( \frac{(2m-1)(j+1) - (2j+1)m}{m(j+1)} \right) u_{j+1} u_{m-1} \\ &= 2 \left( \frac{m-j-1}{m(j+1)} \right) u_{j+1} u_{m-1} \\ &\ge 0, \end{align*}
if 0j<m=nj0 \le j < m = n-j, i.e., 0j<n/20 \le j < n/2. This means that ff decreases steadily over the first n/2n/2 terms and, because f(nj)=f(j)f(n-j) = f(j), then increases, so that
min{f(j):j=0,1,,n}={un/22,if n is even,u(n+1)/2u(n1)/2,if n is odd. \min\{f(j) : j = 0, 1, \dots, n\} = \begin{cases} u_{n/2}^2, & \text{if } n \text{ is even,} \\ u_{(n+1)/2}u_{(n-1)/2}, & \text{if } n \text{ is odd.} \end{cases}

b.
To establish (b), note, with the same notation, that
f(j+1)+f(j1)2f(j)=uj+1um1+uj1um+12ujum=2(2j+1)j+1uj1um1+uj12(2m+1)m+1um2ujum=4(4j21)j(j+1)uj1um1+uj14(4m21)m(m+1)um18(2j1)(2m1)j(m)uj1um1=4uj1um1((4j21)j(j+1)+(4m21)m(m+1)2(2j1)(2m1)jm)=4uj1um13m2+m+3j2+j2jm2j(j+1)m(m+1)=4uj1um1(m+1)(2m1)+(j+1)(2j1)+(jm)2j(j+1)m(m+1)>0. \begin{align*} f(j+1) + f(j-1) - 2f(j) &= u_{j+1}u_{m-1} + u_{j-1}u_{m+1} - 2u_j u_m \\ &= \frac{2(2j+1)}{j+1}u_{j-1}u_{m-1} + u_{j-1} \frac{2(2m+1)}{m+1}u_m - 2u_j u_m \\ &= \frac{4(4j^2-1)}{j(j+1)}u_{j-1}u_{m-1} + u_{j-1} \frac{4(4m^2-1)}{m(m+1)}u_{m-1} \\ &\quad - \frac{8(2j-1)(2m-1)}{j(m)}u_{j-1}u_{m-1} \\ &= 4u_{j-1}u_{m-1} \left( \frac{(4j^2-1)}{j(j+1)} + \frac{(4m^2-1)}{m(m+1)} - \frac{2(2j-1)(2m-1)}{jm} \right) \\ &= 4u_{j-1}u_{m-1} \frac{3m^2+m+3j^2+j-2jm-2}{j(j+1)m(m+1)} \\ &= 4u_{j-1}u_{m-1} \frac{(m+1)(2m-1)+(j+1)(2j-1)+(j-m)^2}{j(j+1)m(m+1)} \\ &> 0. \end{align*}
Hence (b) holds.

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.