The 65th IMO China National Team Selection Test

Proof 1. Consider the set of ordered triples: $$A=\{(u,v,w)\in {\mathbb{N}}^3\mid u,v,w\le m;u+v+w=2m\},$$ $$B=\{(u,v,w)\in {\mathbb{N}}^3\mid u+v+w=2m\},B_1=\{(u,v,w)\in B\mid u\ge m+1\},$$ $$B_2=\{(u,v,w)\in B\mid v\ge m+1\},B_3=\{(u,v,w)\in B\mid w\ge m+1\}.$$ Then $A=B\setminus (B_1\cup B_2\cup B_3)$. Therefore, $$\begin{array}{rl}\text{LHS of (1)}& =\sum _{\begin{array}{c}i,j,k\in \mathbb{N}\\ i+j+k=m\end{array}}{C}_{i+j}{C}_{i+k}{C}_{j+k}=\sum _{(u,v,w)\in A}{C}_u{C}_v{C}_w\\ & =\sum _{(u,v,w)\in B}{C}_u{C}_v{C}_w-\sum _{(u,v,w)\in B_1}{C}_u{C}_v{C}_w-\sum _{(u,v,w)\in B_2}{C}_u{C}_v{C}_w-\sum _{(u,v,w)\in B_3}{C}_u{C}_v{C}_w.\end{array}(2)$$ By symmetry, the sums over $B_1$, $B_2$, and $B_3$ are the same. Using the recurrence relation for Catalan numbers: $$C_{n+1}=\sum _{i=0}^n{C}_i{C}_{n-i}=C_0{C}_n+C_1{C}_{n-1}+\cdots +C_n{C}_0,$$ we have $$\begin{array}{rl}\sum _{(u,v,w)\in B}{C}_u{C}_v{C}_w& =\sum _{u=0}^{2m}{C}_u\left(\sum _{v=0}^{2m-u}{C}_v{C}_{2m-u-v}\right)=\sum _{u=0}^{2m}{C}_u{C}_{2m+1-u}\\ & =\left(\sum _{u=0}^{2m+1}{C}_u{C}_{2m+1-u}\right)-C_{2m+1}{C}_0=C_{2m+2}-C_{2m+1},\end{array}$$ $$\begin{array}{rl}\sum _{(u,v,w)\in B_1}{C}_u{C}_v{C}_w& =\sum _{u=m+1}^{2m}{C}_u\left(\sum _{v=0}^{2m-u}{C}_v{C}_{2m-u-v}\right)=\sum _{u=m+1}^{2m}{C}_u{C}_{2m+1-u}\\ & =\frac{1}{2}\left(\sum _{u=1}^{2m}{C}_u{C}_{2m+1-u}\right)=\frac{1}{2}(C_{2m+2}-2C_{2m+1}).\end{array}$$ Since $$\begin{array}{rl}{C}_{2m+2}& =\frac{(4m+4)!}{(2m+2)!(2m+3)!}=\frac{(4m+3)(4m+4)}{(2m+2)(2m+3)}\cdot \frac{(4m+2)!}{(2m+1)!(2m+2)!}\\ & =\frac{2(4m+3)}{2m+3}\cdot C_{2m+1},\end{array}$$

we have $$\begin{array}{rl}\text{LHS of (1)}& =\sum _{(u,v,w)\in A}{C}_u{C}_v{C}_w=(C_{2m+2}-C_{2m+1})-3\cdot \frac{1}{2}(C_{2m+2}-2C_{2m+1})\\ & =2C_{2m+1}-\frac{1}{2}{C}_{2m+2}=\frac{3}{2m+3}{C}_{2m+1}=\text{RHS of (1).}\square \end{array}$$

Proof 2 (Combinatorial Model). The number of ways to triangulate a convex n-gon $P_1{P}_2\cdots P_n$ by adding n − 3 non-intersecting diagonals is exactly the Catalan number $C_{n-2}$. This result can be proven by induction on $n$. Consider vertex $P_n$. If $P_n$ is not connected by any diagonal, then $P_1$ and $P_{n-1}$ are connected, reducing the problem to the triangulation of a convex $n-1$-gon $P_1{P}_2\cdots P_{n-1}$, which has $C_{n-3}$ ways. If $P_n$ is connected by a diagonal, let $P_k$ ($2\le k\le n-2$) be the smallest vertex connected to $P_n$. Then $P_n$ and $P_k$ are connected, and $P_1$ to $P_{k-1}$ are not connected to $P_n$. This reduces to triangulating a convex $k$-gon $P_1{P}_2\cdots P_k$ and a convex $n-k+1$-gon $P_k{P}_{k+1}\cdots P_n$, which has $C_{k-2}{C}_{n-k-1}$ ways. Summing over $k=2,\dots ,n-2$ and adding $C_{n-3}$, we get: $$(C_0{C}_{n-3}+C_1{C}_{n-4}+\cdots +C_{n-4}{C}_1)+C_{n-3}=C_{n-2}.$$ Now, consider the original problem. Take the regular $2m+3$-gon $P_1{P}_2\cdots P_{2m+3}$ inscribed in a circle. We triangulate the $(2m+3)$-gon and select the unique triangle containing the center (the only acute triangle) and designate one vertex. Consider the total number of such operations. If we first select the designated vertex $P_u$ (with $2m+3$ choices), then draw the triangle $P_u{P}_v{P}_w$ containing the center, with $v-u,w-v$, and $u-w$ modulo $2m+3$ belonging to $\{1,2,\dots ,m+1\}$, and the sum of these residues being $2m+3$. This corresponds to $(i,j,k)\in {\mathbb{N}}^3$ satisfying $i+j+k=m$ and $$v-u\equiv i+j+1,w-v\equiv j+k+1,u-w\equiv k+i+1(\mathrm{mod}2m+3).$$ Then, the three regions between the sides of the triangle can be further triangulated, e.g., the region containing $P_u{P}_v$ is a $i+j+2$-gon, with $C_{i+j}$ ways to triangulate. Thus, the total number of ways is $$(2m+3)\cdot \sum _{\begin{array}{c}i,j,k\in \mathbb{N}\\ i+j+k=m\end{array}}{C}_{i+j}{C}_{i+k}{C}_{j+k}.$$ On the other hand, we can first triangulate the $2m+3$-gon, then choose one of the vertices of the unique triangle containing the center, giving $3C_{2m+1}$ ways. Equating the two results, we get $$(2m+3)\cdot \sum _{\begin{array}{c}i,j,k\in \mathbb{N}\\ i+j+k=m\end{array}}{C}_{i+j}{C}_{i+k}{C}_{j+k}=3C_{2m+1}.$$ Thus, the stated identity holds.