证明某个奇怪的结论:
\[S_{n}(k-t)=\binom{n+k-t}{k-t} \]其中 \(S_n(k-t)\) 为一个长度为 \(k-t\) 的、初始值全为 \(1\) 的序列 \(A\) 的 \(n\) 为前缀和的第 \(k-t\) 项。
不妨把序列 \(A\) 看成一个多项式:
\[f(x)=1+x+x^2+....=\sum_{i=0}^{\infin} x^i \]求它的前缀和,也就是把它乘个 \(G(x)=\sum_{i=0}^{\infin}x^i\) 的多项式。结合生成函数思想,我们初始要求的 \(S_n(k-t)\) 也就是函数
\[h(x)=f(x)\times G^{n}(x) \]的第 \(k-t\) 项。由于 \(f(x)\) 和 \(G(x)\) 是一致的,于是 \(h(x)\) 也可以写成
\[h(x)=\frac{1}{(1-x)^{n+1}}=(1-x)^{-(n+1)} \]利用广义二项式定理展开,得到
\[h(x)=\sum_{i=0}^{\infin} \binom{n+i}{i}x^i \]他的第 \(k-t\) 项就是 \(\binom{n+k-t}{k-t}\) 。