如何推导$[z^n]\frac{z^k}{(1-z)^k}={n-1 \choose k-1}$？计算错在哪？

一、正确推导$[z^n]\frac{zk}{(1-z)^k} = \binom{n-1}{k-1}$ #

我们可以分两步用生成函数的基本性质和牛顿二项式定理来推导：

1. 利用移位性质简化系数提取
   根据生成函数的移位规则：对于任意生成函数$F(z)$，有$[z^n]zm F(z) = [z^{n-m}]F(z)$（当$n < m$时，系数为0）。
   这里$F(z) = (1-z)^{-k}$，$m = k$，所以：
   $$[z^n]\frac{zk}{(1-z)^k} = z^{n-k}^{-k}$$

2. 展开$(1-z)^{-k}$并提取系数
   根据牛顿二项式定理，对于负整数指数的展开：
   $$(1 - z)^{-k} = \sum_{t=0}^{\infty} \binom{-k}{t} (-z)^t$$
   其中负下标组合数的转换公式为$\binom{-k}{t} = (-1)^t \binom{k + t - 1}{t}$（这个公式可以通过组合数递推或生成函数定义验证）。代入后：
   $$(1 - z)^{-k} = \sum_{t=0}^{\infty} (-1)^t \binom{k + t - 1}{t} (-z)^t = \sum_{t=0}^{\infty} \binom{k + t - 1}{t} z^t$$
   现在我们需要提取$z^{n-k}$的系数，令$t = n - k$（这里要求$n \geq k$，否则系数为0），代入得：
   $$z^{n-k}^{-k} = \binom{k + (n - k) - 1}{n - k} = \binom{n - 1}{n - k}$$
   根据组合数的对称性$\binom{a}{b} = \binom{a}{a - b}$，$\binom{n - 1}{n - k} = \binom{n - 1}{k - 1}$，最终得到：
   $$[z^n]\frac{zk}{(1-z)^k} = \binom{n-1}{k-1}$$

二、排查你的计算过程中的错误 #

咱们一步步拆解你写的推导：

第一步：$[z^n]zk\cdot (1-z)^{-k} = z^{n-k}^{-k}$ #

这一步是完全正确的，精准运用了生成函数的移位性质。

第二步：$[z^{n-k}]\displaystyle\sum_{k \geq 0}{n + k - 1 \choose k }(-z)^k(1){-n-k}(-1)^k$ #

这里有三个核心错误：

1. 求和变量名冲突：原式中的$k$是固定参数（分母的指数、分子的$z^k$），但你把求和变量也用了$k$，这会导致后续逻辑混乱，应该换成$t$这类不重复的变量。
2. 牛顿二项式定理误用：$(1-z)^{-k}$的正确展开是$\sum_{t \geq 0} \binom{-k}{t} 1^{-k - t} (-z)^t$，你错误地把组合数写成了$\binom{n +k -1}{k}$，还错误引入了$(1)^{-n -k}$（正确的应该是$(1)^{-k - t}$，因为指数是$-k$）。
3. 多余的符号项：牛顿二项式展开里已经包含了$(-z)^t = (-1)^t z^{t$，不需要再额外乘以$(-1)}k$，属于画蛇添足。

第三步：$[z^{n-k}]\sum_{k \geq 0}{n + k - 1 \choose k }z^k(-1){2k}$ #

这里符号运算$(-1)^k \cdot (-1)^k = (-1)^{2k} = 1$是对的，但由于第二步的组合数和变量名错误，这一步的求和式本身就不成立。

第四步：$[z^{n-k}]\sum_{k \geq 0}{n + k - 1 \choose k }z^k$ #

同样，求和变量$k$和原式参数$k$冲突，且组合数表达式完全错误。正确的求和式应该是$\sum_{t \geq0} \binom{k + t -1}{t} z^{t$，这样才能顺利提取$z}{n-k}$的系数。

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