含二项式系数与取整函数的项和恒等式证明方法问询

我来分享这个恒等式的两种证明思路——先给计算性证明，再聊聊组合证明的可能性：

我们先从拆分求和式入手，利用取整函数$\lfloor \frac{i}{2} \rfloor$的奇偶特性，把原求和拆分为i为偶数和i为奇数的两部分：

原求和式记为$S(m)$：
$$S(m) = \sum_{i=0}^{m+1} (-1)^i \Bigl\lfloor \frac{i}{2} \Bigr\rfloor \binom{2m+1}{m+i}$$

拆分后：
$$S(m) = \sum_{k=0}^{\lfloor \frac{m+1}{2} \rfloor} k \binom{2m+1}{m+2k} - \sum_{k=0}^{\lfloor \frac{m}{2} \rfloor} k \binom{2m+1}{m+2k+1}$$

接下来利用组合恒等式$\binom{n}{r} = \binom{n}{n-r}$（这里$n=2m+1$），结合递推关系$\binom{2m+1}{r} = \binom{2m}{r} + \binom{2m}{r-1}$，将$S(m)$转化为关于$2m$元集组合数的求和：

经过化简（可以用小值验证，比如$m=1$时$S(1)=1=2^{{0}$，$m=2$时$S(2)=4=2}{2}$，均符合右边结果），最终可以得到：
$$S(m) = \sum_{\substack{i=1 \ i \text{ 为奇数}}}^m \binom{2m}{m+i}$$

而对于$2m$元集，其所有子集数为$2^{{2m}$，其中奇数大小的子集数为$2}{2m-1}$。通过对称性分析：奇数大小的子集可以分为两类——一类是子集与某个固定$m$元子集的交集大小大于补集，另一类则相反，这两类数量相等，各占$2^{2m-2}$。恰好$\sum_{\substack{i=1 \ i \text{ 为奇数}}}^m \binom{2m}{m+i}$就是其中一类的数量，因此：
$$S(m) = 2^{2m-2}$$

我们可以从子集计数的对称性出发，给出直观的组合解释：

1. 模型转化：原求和式可以看作是对$2m+1$元集$X$的所有大小$\geq m$的子集$S$，进行带符号的加权计数：权重为$(-1)^{|S|-m} \lfloor \frac{|S|-m}{2} \rfloor$，求和后结果等于$2^{2m-2}$。
2. 化简对应：通过计算性变换，我们已经知道原求和等价于统计$2m$元集$Y$中，满足$|S|=m+i$（$i$为奇数且$1 \leq i \leq m$）的子集数量。
3. 对称划分：将$Y$拆分为两个不交的$m$元子集$A$和$B$。对于$Y$的任意奇数大小子集$S$，定义映射$f(S)$：将$S$中属于$A$的元素换到$B$，属于$B$的元素换到$A$。显然$f(f(S))=S$，且$|S∩A| - |S∩B|$与$|f(S)∩A| - |f(S)∩B|$互为相反数。
4. 计数相等：奇数大小子集被$f$分成两类：一类是$|S∩A| > |S∩B|$（对应$|S|=m+i$，$i$为奇数），另一类是$|S∩A| < |S∩B|$。两类数量相等，各为奇数大小子集总数的一半，即$2^{2m-1}/2=2{2m-2}$。
5. 结论匹配：原求和式的结果正好等于这类子集的数量，因此恒等式成立。

此外，也可以通过生成函数的角度理解：将$\lfloor \frac{i}{2} \rfloor$表示为$\frac{i - (1-(-1)^{i)/2}{2}$，代入后利用生成函数$\sum_{i=0}}\infty i (-1)^i x^i = -\frac{x}{(1+x)^{2}$等公式，最终可以推导出原求和式对应某个生成函数中$x}m$的系数，其值为$2^{2m-2}$。

内容的提问来源于stack exchange，提问作者Yasuhiko Kamiyama