关于Catalan数的组合恒等式（2024年CTST第二轮第1题）

题目：

对自然数，记

是卡塔兰数．求证：对任意自然数，均有

前置知识：

卡塔兰（Catalan）数有非常丰富的性质，在组合计数问题中频繁出现。这里我们只需要知道它的如下性质：

1. 通项公式：

2. 递推公式：

3. 母函数：

4. 组合意义：从原点出发，每次向轴或轴正方向移动个单位，到达点，在移动过程中不越过第一象限平分线的移动方法总数．

参考资料：https://oeis.org/A000108、《命题人讲座——集合与对应》第八讲卡塔兰数

事实上，除了题中已给的通项公式外，使用另外三个性质都能比较快速地证明本题．

但使用母函数需要一定的基础，适合受过母函数训练的同学；使用组合意义则需要一定的灵感，我短时间内没有想到，数之谜上有一个很漂亮的使用组合意义的做法。

这里我们用递推公式进行证明：

证明：

首先化简左边式子，考虑到形式比较复杂，先作换元：

求和下标的条件变为，而

奇偶性相同，故．

但，于是应有．因此

若没有这一条件，比较好计算，可以固定，将改为，这样对的求和可以利用Catalan数的递推公式进行化简，如下：

接下来减去不满足条件的即可，考虑的情况，依然固定：

注意到是对称的，上式补上最后一项，再乘，即可将求和索引改为从到． 于是

再分别考虑的情况，并注意到它们不可能同时发生，于是

只需证明：

这由通项公式是显然的，于是我们完成了本题的证明．