小證明
證明一個不那么直觀的結論：
\[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}\) 。
浙公網安備 33010602011771號