组合恒等式证明的技术问询

给定整数 (r, s, t) 满足 (0 \le r)，(0 \le s) 且 (r+s \le t)，需要证明以下恒等式：
$$\frac{\binom{s}{0}}{\binom{t}{r}} + \frac{\binom{s}{1}}{\binom{t}{r+1}} + \dots + \frac{\binom{s}{s}}{\binom{t}{r+s}} = \frac{t+1}{(t+1-s)\binom{t-s}{r}}.$$

你已经把原式转化为：
$$\frac{1}{\binom{t-s}{r}\binom{t}{s}} \sum_{k=0}^s \binom{r+k}{r}\binom{t-r-k}{t-r-s}$$
这一步非常关键——你已经把分母中分散的组合项统一提取，现在问题的核心就简化为计算这个求和式 (\sum_{k=0}^s \binom{r+k}{r}\binom{t-r-k}{t-r-s})。我给你提供两种可行的思路：

思路1：生成函数法 #

我们可以利用生成函数的卷积性质来计算这个求和式：

1. 先回忆两个生成函数的基本结论：

   • 对于非负整数 (n)，(\sum_{k=0}^\infty \binom{n+k}{n} x^k = \frac{1}{(1-x)^{n+1}})，这对应“可重复选取n类元素”的计数生成函数。
   • 利用组合数对称性 (\binom{n}{k} = \binom{n}{n-k})，把求和式里的第二项变形：(\binom{t-r-k}{t-r-s} = \binom{t-r-k}{s-k})。

2. 构造两个生成函数：

   • 令 (A(x) = \sum_{k=0}^\infty \binom{r+k}{r} x^k = \frac{1}{(1-x)^{r+1}})
   • 令 (B(x) = \sum_{k=0}^\infty \binom{t-r-k}{s-k} x^k)，做变量替换 (m = s - k)，则 (k = s - m)，代入得：
     $$B(x) = x^s \sum_{m=0}^\infty \binom{(t-r-s)+m}{m} x^m = \frac{x^s}{(1-x){t-r-s+1}}$$

3. 求和式 (\sum_{k=0}^s \binom{r+k}{r}\binom{t-r-k}{s-k}) 就是 (A(x) \cdot B(x)) 中 (x^s) 的系数。计算乘积：
   $$A(x) \cdot B(x) = \frac{x^s}{(1-x){(r+1)+(t-r-s+1)}} = \frac{x^s}{(1-x){t-s+2}}$$

4. 求 (x^s) 的系数：根据生成函数结论，(\frac{1}{(1-x)^n}) 中 (x^k) 的系数是 (\binom{n+k-1}{k})，所以这里 (x^s) 的系数为：
   $$\binom{(t-s+2)+s-1}{s} = \binom{t+1}{s}$$

5. 把结果代回你之前的式子：
   $$\frac{1}{\binom{t-s}{r}\binom{t}{s}} \times \binom{t+1}{s} = \frac{(t+1)!}{s!(t+1-s)!} \times \frac{r!(t-s-r)!}{(t-s)!} \times \frac{s!(t-s)!}{t!}$$
   化简后正好得到右边的 (\frac{t+1}{(t+1-s)\binom{t-s}{r}})，恒等式得证。

思路2：组合意义解释 #

我们可以从计数的角度，让等式两边对应同一个问题的两种解法：

• 右边的意义：把 (\frac{t+1}{(t+1-s)\binom{t-s}{r}}) 看成是“从 (t+1) 个元素中选 (r+s+1) 个元素，且标记其中第 (r+1) 个元素（按从小到大排序）”的总方案数的另一种表达。
• 左边的意义：对于每个 (k=0) 到 (s)，(\frac{\binom{s}{k}}{\binom{t}{r+k}}) 对应“固定标记元素的位置，使得前面有 (r+k) 个元素、选 (r) 个，后面选 (s-k) 个”的情况，所有情况累加起来正好和右边的计数结果一致，以此直观验证恒等式成立。

备注：内容来源于stack exchange，提问作者Maths2