小证明

证明某个奇怪的结论:

\[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}\) 。

上一篇:字符串题目:千位分隔数


下一篇:通信原理-数字基带传输