Proof 1. Consider the set of ordered triples:
A={(u,v,w)∈N3∣u,v,w≤m;u+v+w=2m},
B={(u,v,w)∈N3∣u+v+w=2m},B1={(u,v,w)∈B∣u≥m+1},
B2={(u,v,w)∈B∣v≥m+1},B3={(u,v,w)∈B∣w≥m+1}.
Then A=B∖(B1∪B2∪B3). Therefore,
LHS of (1)=i,j,k∈Ni+j+k=m∑Ci+jCi+kCj+k=(u,v,w)∈A∑CuCvCw=(u,v,w)∈B∑CuCvCw−(u,v,w)∈B1∑CuCvCw−(u,v,w)∈B2∑CuCvCw−(u,v,w)∈B3∑CuCvCw.(2)
By symmetry, the sums over B1, B2, and B3 are the same. Using the recurrence relation for Catalan numbers:
Cn+1=i=0∑nCiCn−i=C0Cn+C1Cn−1+⋯+CnC0,
we have
(u,v,w)∈B∑CuCvCw=u=0∑2mCu(v=0∑2m−uCvC2m−u−v)=u=0∑2mCuC2m+1−u=(u=0∑2m+1CuC2m+1−u)−C2m+1C0=C2m+2−C2m+1,
(u,v,w)∈B1∑CuCvCw=u=m+1∑2mCu(v=0∑2m−uCvC2m−u−v)=u=m+1∑2mCuC2m+1−u=21(u=1∑2mCuC2m+1−u)=21(C2m+2−2C2m+1).
Since
C2m+2=(2m+2)!(2m+3)!(4m+4)!=(2m+2)(2m+3)(4m+3)(4m+4)⋅(2m+1)!(2m+2)!(4m+2)!=2m+32(4m+3)⋅C2m+1,
we have
LHS of (1)=(u,v,w)∈A∑CuCvCw=(C2m+2−C2m+1)−3⋅21(C2m+2−2C2m+1)=2C2m+1−21C2m+2=2m+33C2m+1=RHS of (1).□
Proof 2 (Combinatorial Model). The number of ways to triangulate a convex n-gon P1P2⋯Pn by adding n − 3 non-intersecting diagonals is exactly the Catalan number Cn−2.
This result can be proven by induction on n. Consider vertex Pn. If Pn is not connected by any diagonal, then P1 and Pn−1 are connected, reducing the problem to the triangulation of a convex n−1-gon P1P2⋯Pn−1, which has Cn−3 ways. If Pn is connected by a diagonal, let Pk (2≤k≤n−2) be the smallest vertex connected to Pn. Then Pn and Pk are connected, and P1 to Pk−1 are not connected to Pn. This reduces to triangulating a convex k-gon P1P2⋯Pk and a convex n−k+1-gon PkPk+1⋯Pn, which has Ck−2Cn−k−1 ways. Summing over k=2,…,n−2 and adding Cn−3, we get:
(C0Cn−3+C1Cn−4+⋯+Cn−4C1)+Cn−3=Cn−2.
Now, consider the original problem. Take the regular 2m+3-gon P1P2⋯P2m+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 Pu (with 2m+3 choices), then draw the triangle PuPvPw
containing the center, with v−u,w−v, and u−w modulo 2m+3 belonging to {1,2,…,m+1}, and
the sum of these residues being 2m+3. This corresponds to (i,j,k)∈N3 satisfying i+j+k=m
and
v−u≡i+j+1,w−v≡j+k+1,u−w≡k+i+1(mod2m+3).
Then, the three regions between the sides of the triangle can be further triangulated, e.g., the
region containing PuPv is a i+j+2-gon, with Ci+j ways to triangulate.
Thus, the total number of ways is
(2m+3)⋅i,j,k∈Ni+j+k=m∑Ci+jCi+kCj+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 3C2m+1 ways.
Equating the two results, we get
(2m+3)⋅i,j,k∈Ni+j+k=m∑Ci+jCi+kCj+k=3C2m+1.
Thus, the stated identity holds.